704.二分查找

题目链接：704.二分查找

分析

假设答案所处的区间在 [a, b) 的区间内(a,b满足al ,因为 l>=r 时区间不合法。

以此为基础，每次对 l 和 r 的迭代都需要在不影响正确性的前提下尽可能缩小区间。

这也是为什么 r = mid 但 l = mid+1。

如果采用 r = mid 和 l = mid 的写法，反而有可能得出错误答案。

eg

nums =

[-1,0,3,5,9,12]

target =

2

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size();
        while (l < r) {
            int mid = l + ((r-l) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) l = mid+1;
            else r = mid;
        }
        return -1;
    }
};