算法-二分查找

适用条件:

有序的数组

时间复杂度:

\theta (logN)


题型:

1. exactly查找这个数

nums[mid] == target

2. 查找第一个不小于目标值的数,可变形为查找最后一个小于目标值的数

if(nums[mid] < target)

我们已经找到了第一个不小于目标值的数,指向right,那么再往前退一位,返回 right - 1,就是最后一个小于目标值的数。

3. 查找第一个大于目标值的数,可变形为查找最后一个不大于目标值的数

if(nums[mid] <= target)

返回最后一个相同数字的下一个位置



注意事项

1. m = l + (r-l)/2

为什么不用m=(l+r)/2,防止数值过大溢出

2. right的初始化,可以写成nums.size()或者nums.size()-1

3. left和right的关系,可以写成left < right或者left <= right

4. 更新right的赋值,可以写出right = mid或者right = mid - 1

5. 最后返回值,可以返回left, right, 或者right - 1

但是这些不同的写法并不能随机的组合,比如,若 right 初始化为了 nums.size(),那么就必须用 left < right,而最后的 right 的赋值必须用 right = mid。

但是如果我们 right 初始化为 nums.size() - 1,那么就必须用 left <= right,并且right的赋值要写成 right = mid - 1,不然就会出错。

建议选择一套自己喜欢的写法,并且记住,实在不行就带简单的例子来一步一步执行,确定正确的写法也行。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容