标准二分查找左边界模板

二分查找作为程序员的一项基本技能，是面试官最常使用来考察程序员基本素质的算法之一，也是解决很多查找类题目的常用方法，它可以达到  的时间复杂度。

前提条件

必须有序。一般是从小到大有序。

坑点

计算中间值导致的数据越界。一般我们都是定义左边界（left）和右边界（right）都使用 int 类型，如果 left 和 right 足够大，mid = (left + right)/2，可能会由于 left+right 导致 int 数据类型越界。所以安全的写法是 mid = left + ((right - left) >> 1) 或者 mid = left + (right - left) / 2，推荐使用右移操作，因为右移比除法快。

模板类型

利用二分法寻找左边界是二分查找的一个变体，应用它的题目常常有以下几种特性之一：

1. 数组有序，但包含重复元素
2. 数组部分有序，且不包含重复元素
3. 数组部分有序，且包含重复元素

左边界查找类型1

本类型包括了上面说的第一种，第二种情况。

C++模板代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left)>>1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

程序解读

1、循环条件： left < right 。和标准二分查找不同。因为在最后 left 与 right 相邻的时候，mid 和 left 处于相同的位置（mid 偏左）；则下一步，无论怎样，left，mid，right 都将指向同一个位置，如果此时循环的条件是 left <= right，则我们需要再进入一遍循环，此时，如果nums[mid] < target还好说，循环正常终止；否则，我们会令 right = mid，这样并没有改变 left，mid，right 的位置，将进入死循环。

2、中间位置计算： mid = left + ((right -left) >> 1)。

3、左边界更新：left = mid + 1 。

4、右边界更新： right = mid 。和标准二分查找不同。因为我们需要在找到目标值后，继续向左寻找左边界。

5、返回值： nums[left] == target ? left : -1 。和标准二分查找不同。我们只需要遍历到 left 和 right 相邻的情况就行了，因为这一轮循环后，无论怎样，left，mid，right 都会指向同一个位置，而如果这个位置的值等于目标值，则它就一定是最左侧的目标值；如果不等于目标值，则说明没有找到目标值。

左边界查找类型2

本类型包括了上面说的第三种，用于数组部分有序且包含重复元素的情况。这种条件下在我们向左收缩的时候，不能简单的令 right = mid，因为有重复元素的存在，这会导致我们有可能遗漏掉一部分区域，此时向左收缩只能采用比较保守的方式。

C++模板代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) >> 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

程序解读

与类型 1 的唯一区别就在于对右侧值的收缩更加保守。这种收缩方式可以有效地防止我们一下子跳过了目标边界从而导致了搜索区域的遗漏。