二分查找 #

1、有序数组，查找一个数搜索一个数，如果存在，返回其索引，否则返回 -1。 #

int binarySearch(vector<int>& nums, int target) {    int left = 0;
    int right = nums.size() - 1; // 注意
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        else if(nums[mid] == target)
            return mid;
    }
    return -1;
}

1、为什么 while 循环的条件中是 <=，而不是 <？ #

答：因为初始化right的赋值是nums.length - 1，每次进行搜索的区间，相当于两端都闭区间[left, right]。while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

while(left <= right)的终止条件是left == right + 1，写成区间的形式就是[right + 1, right]，这时候区间为空，所以这时候 while 循环终止是正确的，直接返回 -1 即可。

while(left < right)的终止条件是left == right，写成区间的形式就是[right, right]，或者带个具体的数字进去[2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间[2, 2]被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

2、为什么left = mid + 1，right = mid - 1？我看有的代码是right = mid或者left = mid，没有这些加加减减，到底怎么回事，怎么判断？ #

答：本算法的搜索区间是两端都闭的，即[left, right]。那么当我们发现索引mid不是要找的target时，下一步应该去搜索哪里呢？当然是去搜索[left, mid-1]或者[mid+1, right]对不对？因为mid已经搜索过，应该从搜索区间中去除。

3、此算法有什么缺陷？ #

答：比如说给你有序数组nums = [1,2,2,2,3]，target为 2，此算法返回的索引是 2，没错。但是如果我想得到target的左侧边界，即索引 1，或者我想得到target的右侧边界，即索引 3，这样的话此算法是无法处理的。这样的需求很常见，你也许会说，找到一个 target，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的复杂度了。

2、有序数组，寻找左侧边界 #

int left_bound(int[] nums, int target) {    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else{
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.size() || nums[left] != target)
        return -1;
    return left;
}

1、为什么 while 中是<而不是<=? #

答：每次循环的「搜索区间」是[left, right)左闭右开。 while(left < right)终止的条件是left == right，此时搜索区间[left, left)为空，所以可以正确终止。

2、如果nums中不存在target这个值，怎么办？ #

左侧边界的特殊含义：nums中小于 target 的元素有 left 个。

3、为什么left = mid + 1，right = mid？和之前的算法不一样？ #

答：这个很好解释，因为我们的「搜索区间」是[left, right)左闭右开，所以当nums[mid]被检测之后，下一步的搜索区间应该去掉mid分割成两个区间，即[left, mid)或[mid + 1, right)。

4、为什么该算法能够搜索左侧边界？ #

答：关键在于对于nums[mid] == target这种情况的处理。找到 target 时不要立即返回，而是缩小「搜索区间」的上界right，在区间[left, mid)中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

3、有序数组，寻找右侧边界 #

int right_bound(int[] nums, int target) {    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}