前言

虽然二分就那么简单的几行代码，但是我之前一直搞不懂里面的一些判断是不是要加等于号，更新边界要不要加1或者减1。
每次写的时候就玄学写，可能成功，也可能死循环。但是，其实只要明确了「搜索区间」和「收缩逻辑」，执行逻辑不漏掉元素，就很好办了。
初学编写代码时，我们习惯条件判断中的将最后一个分支经常被else代替，或者如果两个分支条件的执行逻辑相同时将两个分支合二为一，我觉得这样对思考二分流程是不利的。
另外，整数溢出的问题已经是老生常谈了，少用(l + r) / 2，改用l + (r - l) >> 1。
​

查找元素

常用模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int m = l + ((r - l) >> 1);
        if (nums[m] == target)
            return m;
        else if (nums[m] < target)
            l = m + 1;
        else if (nums[m] > target)
            r = m - 1;
    }
    return -1;
}

这里我习惯使用闭区间进行搜索，这样收缩区间时候的+1和-1逻辑也是对称的，很好记忆。

（1）搜索区间

这里搜索闭区间[l, r]，终止条件为l = r + 1，因为这时候[r + 1, r]为空区间。
如果将终止条件改为l = r，那么终止时候闭区间为[r, r]，它还包含一个数nums[r]，在返回时候判断一下nums[r]与target的大小即可。

（2）收缩逻辑

  1. 如果nums[m] < target，说明[l, m]整个区间都小于target，因此接下来向右收缩，搜索[m + 1, r]即可，于是我们把l更新为m + 1。
  2. 如果nums[m] > target，说明[m, r]整个区间都大于target，因此接下来向左收缩，搜索[l, m - 1]即可，于是我们把r更新为m - 1。

查找左边界

常用模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int searchLeft(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int m = l + ((r - l) >> 1);
        if (nums[m] == target)
            r = m;
        else if (nums[m] < target)
            l = m + 1;
        else if (nums[m] > target)
            r = m;
    }
    if (l >= nums.length || nums[l] != target)
        return -1;
    return l;
}

（1）搜索区间

这里搜索区间[l, r)，终止条件为l = r，因为这时候区间[r, r)是一个空区间。

（2）收缩逻辑

  1. 如果nums[m] = target，这时候刚好找到了target，不要立即返回，而是缩小区间的右边界，将r更新为m，在区间[l, m)中继续搜索，不断向左收缩，达到锁定左侧边界的目的。
  2. 如果nums[m] < target，说明[l, m]整个区间都小于target，因此接下来向右收缩，搜索[m + 1, r]即可，于是我们把l更新为m + 1。
  3. 如果nums[m] > target，说明[m, r]整个区间都大于target，因此接下来向左收缩，搜索[l, m]即可，于是我们把r更新为m。

（3）越界情况

如果目标数字比数组最后一个数字还要大，那么循环结束后l = nums.length，因此需要做一个越界判断。
比如在[2, 2]中查找3，那么步骤如下：

步骤 执行前(l, r) m 执行后(l, r)
1 (0, 2) 1 (2, 2)

循环结束，l = r = 2，已经越界，所以需要判断。

（4）双闭写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int searchLeft(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int m = l + ((r - l) >> 1);
        if (nums[m] == target)
            r = m - 1;
        else if (nums[m] < target)
            l = m + 1;
        else
            r = m - 1;
    }
    if (l >= nums.length || nums[l] != target)
        return -1;
    return l;
}

查找右边界

常用模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int searchRight(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int m = l + ((r - l) >> 1);
        if (nums[m] == target)
            l = m + 1;
        else if (nums[m] < target)
            l = m + 1;
        else if (nums[m] > target)
            r = m;
    }
    if (l - 1 < 0 || nums[l - 1] != target) 
        return -1;
    return  l - 1;
}

（1）搜索区间

在循环中搜索左闭右开区间[l, r)，终止条件l = r。
但是，注意if (nums[m] == target) l = m + 1这个语句，一旦nums[m]与target相等，l就等于m+1，所以循环结束之后，nums[l]必然不等于target，最终l比右边界大1，返回的时候需要把l-1。

（2）收缩逻辑

  1. 如果nums[m] = target，这时候刚好找到了target，不要立即返回，而是缩小区间的左边界，将l更新为m + 1，在区间[m + 1, r)中继续搜索，不断向右收缩，达到锁定右侧边界的目的。
  2. 如果nums[m] < target，说明[l, m]整个区间都小于target，因此接下来向右收缩，搜索[m + 1, r]即可，于是我们把l更新为m + 1。
  3. 如果nums[m] > target，说明[m, r]整个区间都大于target，因此接下来向左收缩，搜索[l, m]即可，于是我们把r更新为m。

（3）越界情况

如果目标数字比数组第一个数字还要大，那么循环结束后l = 0，因此需要做一个越界判断。
比如在[2, 2]中查找1，那么步骤如下：

步骤 执行前(l, r) m 执行后(l, r)
1 (0, 2) 1 (0, 1)
2 (0, 1) 0 (0, 0)

循环结束，l = r = 0，(l - 1)已经越界，所以需要判断。
​

力扣练习

题型1：二分下标（在数组中查找符合条件的元素的下标）
一般而言这个数组是有序的，也可能是半有序的（旋转有序数组或者山脉数组）。

题目
704. 二分查找（简单）
34. 在排序数组中查找元素的第一个和最后一个位置（中等）
33. 搜索旋转排序数组（中等）
81. 搜索旋转排序数组 II（中等）
153. 寻找旋转排序数组中的最小值（中等）
154. 寻找旋转排序数组中的最小值 II（中等）
300. 最长上升子序列（中等）
852. 山脉数组的峰顶索引（简单）
1095. 山脉数组中查找目标值（中等）
4. 寻找两个有序数组的中位数（困难）
658. 找到 K 个最接近的元素（中等）

题型2：二分答案（在一个有范围的区间里搜索一个整数）
定位一个有范围的整数，这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数，这个整数有明确的范围，可以考虑使用二分查找。

题目
69. 平方根（简单）
287. 寻找重复数（中等）
374. 猜数字大小（简单）
1300. 转变数组后最接近目标值的数组和

题型3：二分答案的升级版（判别条件需要遍历数组）

题目
410. 分割数组的最大值（困难）
875. 爱吃香蕉的珂珂（中等）
LCP 12. 小张刷题计划（中等）
1482. 制作 m 束花所需的最少天数（中等）
1552. 两球之间的磁力（中等）

参考资料

[1] 💤 labuladong力扣T704题解
[2] 💫 liweiwei哥哥力扣T35题解
​