适用条件:
有序的数组
时间复杂度:
题型:
1. exactly查找这个数
nums[mid] == target
2. 查找第一个不小于目标值的数,可变形为查找最后一个小于目标值的数
if(nums[mid] < target)
我们已经找到了第一个不小于目标值的数,指向right,那么再往前退一位,返回 right - 1,就是最后一个小于目标值的数。
3. 查找第一个大于目标值的数,可变形为查找最后一个不大于目标值的数
if(nums[mid] <= target)
返回最后一个相同数字的下一个位置
注意事项
1.
为什么不用,防止数值过大溢出
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,不然就会出错。
建议选择一套自己喜欢的写法,并且记住,实在不行就带简单的例子来一步一步执行,确定正确的写法也行。