二分搜索套路框架

二分查找是在一个有序数组中找到目标元素的一种查找方法，它的大致思想是：将区间分为两半，对比目标元素是在左半边还是右半边，然后递归地在左（右）半边区间进行查找。

二分搜索分为三类：

  1. 寻找某个数
  2. 寻找某个数的左边界
  3. 寻找某个数的右边界

虽然这三类看似差不多，主要框架也差不多，但是在细节上是有所区别的，所以本节内容是主要讲解细节上面的差异，搞懂这些细节上的差异，是我们这一节的目的。既然只有细节上有差距，那么先来看一下总的框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int binarySearch(int[] nums, int target){
    //细节1 区间的表示形式
    int left = 0;
    int right = nums.length - 1;

    //细节2 while()里是 < 还是 <=
    while(left <= right){
      int mid = left + (right - left) / 2;

      //细节3 “...”中我们应该如何改变搜索边界
      if(nums[mid] == target){
          //...
      }else if(nums[mid] < target){
          //...
      }else if(nums[mid] > target){
          //...
      }
    }

    //细节4 如何返回索引，该返回哪个值
    return ...;
}

细节介绍

其实这些细节都是有联系的我们一个一个来看:

细节1：二分查找的区间表示形式
1.left, right = 0, nums.length-1, 这种方法指的是指left指向第一个元素,right指向最后一个元素，是一个左闭右闭区间，用数学的语言来表示就是“[a, b]”。
2.left, right = 0,nums.length, 这种方法指的是left指向第一个元素，right指向最后一个元素，是一个左闭右开区间，用数学的语言来表示就是“[a, b)”。

其实细节1讲述了描述左右边界的定义，两个指针分别代表什么含义，在下面的内容中，都将用这些定义来描述区间范围。

细节2：while()循环里的条件使用“<”还是“<=”
该问题就需要考虑细节1中用的是那种表示形式来表达区间了，因为while()循环里的条件是需要继续查找的条件，那什么是中止条件呢？答：区间为空的时候。下面用细节1中的两个表示形式来举例：
[a, b] 左闭右闭区间：循环在a <= b 时都可以继续查找，因为在a <= b 时，[a, b] 中是有元素的，所以应当使用“<=”。中止条件是left == right+1。
[a, b) 左闭右开区间：循环在a < b 时都可以继续查找，因为在a < b 时，[a, b) 中是有元素的，所以应当使用“<”。中止条件是left == right。

注： 当然区间表示方法不止这两种，你也可以自己定义。但是循环里的条件就取决于区间表示形式，所以细节2是依赖于细节1的。至于为什么是中止条件是这两个，模拟一下就行啦。

细节3：各个条件中指针该怎么转移
转移的方式其实只有两种：
1.左指针向右移，这代表着目标元素在右半边，那怎样才能将左指针移动到能够完整的包含右半边所有元素呢？这就需要参考细节1中的表示形式，[a, b]的话就需要left = mid + 1,因为小于等于mid的都已经考虑过了，[mid+1, right]包括了所有右半边的元素。[a, b)的话就需要left = mid+1，因为mid访问过了，而left指的是左指针，是闭区间，两种形式都是闭区间，所以转移方式相同
2.右指针向左移，这代表着目标元素在做半边。[a, b]的话就需要right = mid - 1，因为mid访问过了。而[a, b)中是不一样的，它的右指针指的是最右元素的下一个位置，最后一个元素是mid-1，所以right = mid。

当然，这两种方式具体放在哪里还需要考虑是哪一类的二分搜索。

细节4等到3种二分搜索介绍完再说

三类二分搜索具体介绍

为了减少篇幅，这里只介绍区间表示为左右都闭的方式
1.寻找某个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(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){
            return mid;//找到啦
        }else if(nums[mid] < target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid -1;
        }
    }
    return -1;//没找到呢
}

这里都是闭区间，所以采用left = mid + 1和right = mid - 1来转移指针。但是如果nums[]中好几个元素等于target，那就产生了“target的左侧边界”和“target的右侧边界”的需求。
2.寻找左侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int left_bound(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){
            right = mid - 1;//[1]
        }else if(nums[mid] < target){
            left = mid + 1;//[2]
        }else if(nums[mid] > target){
            right = mid - 1;//[3]
        }
    }
    if(left >= nums.length || nums[left] != target){
        return -1;
    }
    return left;
}
 1 2 2 2 3 34 4 5 9

由于都是闭区间，所以采用的转移指针方式和循环条件都是确定的。[2]和[3]都很好理解，属于我们的常规操作，那么[1]又是怎么理解的呢？看这个之前我们需要了解在找不到的情况下，左右指针分别在什么位置。中止条件是left == right + 1,找不到的数大于right，小于left。
现在再来理解[1]，为了寻找左侧边界即使找到了target，也要继续往左边找，这不就是要找小于target的第一个数嘛。虽说是要找小于target的第一个数，但是这个数并不存在，所以，中止条件只能像是这样，就像这样，left刚好落在了最左边的target上。就是我们找到的最终目标，只要返回left就行了。
但是新问题又来了，如果本身就没有target怎么办？那只要判断一下是不是nums[left]是不是target就行了，但是这里又有个细节，left是可能超出num[]范围外的，left的取值范围是[0, nums.length]，nums[nums.length]可能右溢出，所以需要先判断是否右溢出。如果不存在的话，就返回-1。
3.寻找右侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int left_bound(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){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid - 1;
        }
    }
    if(right < 0 || nums[right] != target){
        return -1;
    }
    return right;
}

基本与找左侧边界类似，便不再赘述了。