Loading... # 问题 今天做了一个分查找得题,这个就是学C必备得题吧。当时感觉有手就行 ```cpp class Solution { public: int search(vector<int>& nums, int target) { int left = 0, high = nums.size() - 1, mid; while(left <= high){ mid = (left + high)/2; if(nums[mid] == target){ break; }else if(nums[mid] > target) { high = mid - 1; }else{ left = mid + 1; } } if(left > high) mid = -1; return mid; } }; ``` 可是…… 出错了,后来才知道在是在`mid = (left + high)/2` 里面得 left + high 有可能超过了 int 范围。 这真的是魔鬼细节啊。 # 解决方法 ```cpp // 这样可以保证不超过 int 范围 int mid = left + (high - left) / 2; //当然还有 mid = l / 2 + r / 2 + (l % 2 == 1 && r % 2 == 1 ? 1 : 0); //其实可以 mid=(l>>1)+(r>>1)+((l&1)&&(r&1)); //捕捉位运算萌新qvq ``` <div class="tip inlineBlock success"> 今天学到的,不能用(left+right)/2形式,当 left 和 right 都是i nt,两个值的初始值都超过int限定大小的一半,那么left+right就会发生溢出,所以应该用left+(right-left)/2来防止求中值时候的溢出。 </div> 最后修改:2021 年 09 月 12 日 © 禁止转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏
2 条评论
学到了 left+(right-left)/2 == (right-left)/2,而且还防止int值溢出,牛蛙!牛蛙!
开始我也不明白