算法总结之二分法模板

前言

二分查找算法作为一种常见的查找方法，将原本是线性时间提升到了对数时间范围，大大缩短了搜索时间，具有很大的应用场景，而在 LeetCode 中，要运用二分搜索法来解的题目也有很多，但是实际上二分查找法的查找目标有很多种，而且在细节写法也有一些变化。

问题形式：

二分查找算法充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用 O(logN) 完成搜索任务。
题目问法大致有这几种

• 查找和目标值完全相等的数
• 查找区间的某个边界值
• 利用子函数对中间值进行判断，确定查找的方向
• 利用二分思想查找函数的极大值

解题思路与模板

根据前面的描述可以看出，这类问题的核心就是在于确定三要素：搜索区间，终止条件和折半方向。

标准二分查找

/** 元素按升序排列，下同 */
int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) >>> 1; // 无符号右移，即使前面溢出也能得到正确结果
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1; // 当前元素比目标值小，则收缩左边界，查找右半边
        } else if (arr[mid] > target) {
            right = mid - 1; // 当前元素比目标值小，则收缩右边界，查找左半边
        }           
    }
    return -1; // 未找到
}

Q：为什么 while 循环的终止条件是 left <= right ？而我看到有的代码里是 left < right ?
A：两者都可以使用，但它们代表不同的搜索区间，需要配合不同的右侧边界。带个例子来看，假如我们在 [ 1 , 3 , 5 , 7 , 9 ] [1,3,5,7,9] [1,3,5,7,9] 中搜索元素 3 3 3 的索引位置。我们在代码里加一些输出语句来看看吧。

循环条件是 left <= right 时
第 1 次循环开始：left = 0, right = 4, mid = 2
第 1 次循环结束：left = 0, right = 1, mid = 2
第 2 次循环开始：left = 0, right = 1, mid = 0
第 2 次循环结束：left = 1, right = 1, mid = 0
第 3 次循环开始：left = 1, right = 1, mid = 1
找到了 target = 3 ，索引是 1

结果正确。下面我们把 <= 改为 <，其他条件不变

循环条件是 left < right 时
第 1 次循环开始：left = 0, right = 4, mid = 2
第 1 次循环结束：left = 0, right = 1, mid = 2
第 2 次循环开始：left = 0, right = 1, mid = 0
第 2 次循环结束：left = 1, right = 1, mid = 0
未找到 target = 3

出现了错误！我们注意到在第二次循环结束时已经有 l e f t = r i g h t ，不满足第三次循环开始条件了。导致了 m i d mid mid 遗漏了索引 1 的位置。如果我们一定要用left<right 作为循环条件呢？可以通过修改右侧边界的方式来实现，看下面的代码。

/** 使用 while (left < right) 时的正确代码，注意 right 的取值 */
int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length; // 注意这里
    while (left < right) { // 改用 "<"
        int mid = (left + right) >>> 1;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid; // 注意这里
        }           
    }
    return -1;
}

这次我们看到了正确的结果。

循环条件是 left < right 时
第 1 次循环开始：left = 0, right = 5, mid = 2
第 1 次循环结束：left = 0, right = 2, mid = 2
第 2 次循环开始：left = 0, right = 2, mid = 1
找到了 target = 3 ，索引是 1

通过上面的比较不难发现，当使用 l e f t ≤ r i g h t 时，相当于是在闭区间 [ l e f t , r i g h t ]进行搜索；而当使用left<right 时，相当于是在左闭右开区间[left,right) 进行搜索。对于以上两种形式，如果你已经理解了边界的概念，记住它们自然不在话下。

Q：标准算法有什么局限性？
A：至此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。比如说给你数组 [ 1 , 3 , 3 , 3 , 4 ] [1,3,3,3,4] [1,3,3,3,4]，需要搜索元素 3 3 3 的索引，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。然而这样的需求很常见。你也许会说，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以但是不好，假如有大量的重复元素，那样就难以保证二分查找对数级的复杂度了。下面我们就来讨论边界的二分查找算法。

---

模板2：寻找第一个不小于目标值的位置

我们注意到在上面的例子中，要找到元素 3 3 3 的左侧边界，相当于是要找到第一个不小于元素 3 3 3 的位置，我们只需要修改两处代码就能实现。

int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (arr[mid] == target) {
            right = mid; // 注意这里
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid;
        }           
    }
    return right; // 注意这里，也可以写为left, 循环终止时它们是相等的
}

Q：为什么这样能找到左边界？
A：关键在于对找到target 后这种情况的处理，我们并没有直接返回索引值，而是继续收缩右边界令 r i g h t = m i d ，最终达到锁定左边界的目的。

Q：为什么没有返回 -1 的操作？如果数组不存在这样的 target 该怎么办？
A：我们继续通过打印输出结果来看，假如我们在 [ 0 , 1 , 3 , 3 , 3 , 7 , 8 ] [0,1,3,3,3,7,8] [0,1,3,3,3,7,8] 中搜索元素 3 3 3

开始查找，target = 3
第 1 次循环开始：left = 0, right = 7, mid = 3
第 1 次循环结束：left = 0, right = 3, mid = 3
第 2 次循环开始：left = 0, right = 3, mid = 1
第 2 次循环结束：left = 2, right = 3, mid = 1
第 3 次循环开始：left = 2, right = 3, mid = 2
第 3 次循环结束：left = 2, right = 2, mid = 2
结束查找，索引是 2

结果是索引 2，也就是第一个 3 3 3 的位置，正确。然后我们来看下搜索元素 4 4 4

开始查找，target = 4
第 1 次循环开始：left = 0, right = 7, mid = 3
第 1 次循环结束：left = 4, right = 7, mid = 3
第 2 次循环开始：left = 4, right = 7, mid = 5
第 2 次循环结束：left = 4, right = 5, mid = 5
第 3 次循环开始：left = 4, right = 5, mid = 4
第 3 次循环结束：left = 5, right = 5, mid = 4
结束查找，索引是 5

结果是索引 5，也就是元素 7 7 7 的位置。不难看出我们找到了不小于目标值的第一个位置。实际上在 C++ 标准库中有专门的函数 lower_bound，替我们实现了同样的功能。此外，该类问题还可以变形为寻找最后一个小于目标值的位置。我们只需要在返回结果那里继续左移一步，改为 return right - 1 就可以了。

---

模板3：寻找第一个大于目标值的位置

有了上面的分析，那么这里就很容易理解了。对于这种情况，我们需要不断收缩左侧边界，来看代码。

int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (arr[mid] == target) {
            left = mid + 1; // 注意这里
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid;
        }           
    }
    return right; // 注意这里，也可以写为left, 循环终止时它们是相等的
}

再来看下输出结果吧，我们仍然在 [ 0 , 1 , 3 , 3 , 3 , 7 , 8 ] [0,1,3,3,3,7,8] [0,1,3,3,3,7,8] 中搜索元素 3 3 3

开始查找， target = 3
第 1 次循环开始：left = 0, right = 7, mid = 3
第 1 次循环结束：left = 4, right = 7, mid = 3
第 2 次循环开始：left = 4, right = 7, mid = 5
第 2 次循环结束：left = 4, right = 5, mid = 5
第 3 次循环开始：left = 4, right = 5, mid = 4
第 3 次循环结束：left = 5, right = 5, mid = 4
找到了，索引是 5

找到了第一个大于 3 3 3 的元素 7 7 7 了！同样在 C++ 标准库中有专门的函数 upper_bound 实现了该功能。然后你可能会问，那我们要找最后一个 3 3 3 的位置（即右边界）该怎么办？非常简单，只需要在返回值那里左移一步就行了，改为 return right - 1。

---

具体问题

搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例

输入：
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出:：true

解题思路
注意题目中的关键字高效，升序，并且每行第一个整数大于前一行最后一个整数。那么假设我们把矩阵逐行排列拉成一条线，不难看出其实它就变成了一个升序的数组。题目也就变成了在升序数组中找一个目标值，说明就能愉快地二分查找了。我们可以通过一些简单的坐标计算来把矩阵模拟成一个数组。

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int m = matrix.length, n = matrix[0].length;
    // 根据题意不难发现矩阵内第一个元素一定最小，最后一个元素一定最大，如果 target 不在范围内直接返回 false
    if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) return false; 
    int left = 0, right = m * n;
    while (left < right) {
        int mid = (left + right) >>> 1;
        // 根据总元素的个数计算矩阵坐标
        if (matrix[mid / n][mid % n] == target) {
            return true;
        } else if (matrix[mid / n][mid % n] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return false;
}

找到 K 个最接近的元素

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

示例

输入：[1,2,3,4,5], k=4, x=3
输出：[1,2,3,4]

解题思路

题目中说到有序数组，并且是连续区间。区间长度是固定的，并且 k k k 的值为正数，且总是小于给定排序数组的长度 s i z e size size。因此，只要我们找到了左边界的索引，从左边界开始取 k k k 个数，就找到了结果。那么问题就变成了寻找最优区间的左边界。
首先我们讨论左区间的取值范围，使用具体的例子，就很很清楚地找到规律：

• 假设一共有 5 个数， [ 0 , 1 , 2 , 3 , 4 ] [0,1,2,3,4] [0,1,2,3,4]，找 3 个数，左边界最多到元素 2 2 2。
• 假设一共有 8 个数， [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ] [0,1,2,3,4,5,6,7] [0,1,2,3,4,5,6,7]，找 5 个数，左边界最多到元素 3 3 3。

因此，最优区间的左边界的索引的搜索区间为 [ 0 , s i z e − k ] [0, size - k] [0,size−k]，这也就是我们二分查找的范围。然后每次取中间值 m i d mid mid 作为左边界，则待选区间为 [ m i d , m i d + k ] [mid, mid + k] [mid,mid+k]。 这里的二分查找方向比较难想，是通过比较区间两端和 x x x 的距离来确定的，所有情况如下图。

• 如果 x x x 离 m i d mid mid 端更近，则说明我们可以进一步收缩右边界，即 r i g h t = m i d right = mid right=mid。特别地，题目中指出两个值和 x x x 的差值一样时取较小值（也就是 x x x 恰好位于区间中间）。那么这种情况下也需要收缩右边界。
• 如果 x x x 离 m i d + k mid+k mid+k 端更近，则说明我们可以进一步收缩左边界，即 l e f t = m i d + 1 left = mid + 1 left=mid+1

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    int left = 0, right = arr.length - k;
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (x - arr[mid] > arr[mid + k] - x) { // 通过比较区间端点和 x 的距离确定二分方向
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    List<Integer> list = new ArrayList<>();
    for (int i = left; i < left + k; i++) {
        list.add(arr[i]);
    }
    return list;
}

---

其它二分法的练习题：

4. 寻找两个有序数组的中位数
5. 搜索旋转排序数组
6. 在排序数组中查找元素的第一个和最后一个位置
7. Pow(x, n)
8. x 的平方根
9. 寻找旋转排序数组中的最小值
10. 寻找旋转排序数组中的最小值 II
11. 寻找峰值
12. 第一个错误的版本
13. 寻找重复数
14. 长度最小的子数组
15. 两个数组的交集
16. 两个数组的交集 II
17. 有效的完全平方数
18. 猜数字大小
19. 分割数组的最大值
20. 四数相加 II
21. 找到 K 个最接近的元素
22. 二分查找
23. 找出第 k 小的距离对