算法 | 下次面试遇到二分查找，别再写错了

作者: 彭旭锐 | 来源:发表于2021-02-21 02:52 被阅读0次

点赞关注，不再迷路，你的支持对我意义重大！

Hi，我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见已收录，这里有 Android 进阶成长路线笔记 & 博客，欢迎跟着彭丑丑一起成长。（联系方式在 GitHub）

前言

二分查找也称折半查找（Binary Search），是一种效率较高的查找方法（对数时间复杂度），也是面试中经常考到的问题。虽然它的思想很简单，但据《编程珠玑》所述，二分查找算法的实现是极易犯错的，典型的 “一听就懂，一写就错”。 在算法面试中，如果能表现出迅速将自己的思考转变为代码并清晰写在白板上的能力，你的表现会优于只会夸夸其谈而写不出代码的人。

1. 二分查找基础

1.1 问题描述

二分查找的基本问题是：给定一个无重复的有序整型数组，数组大小在 $[1,10000]$ 之间，查找目标数 t 在数组中的索引，不存在则返回 -1。

1.2 算法描述

二分查找算法的核心思想是：减治，即逐渐缩小包含目标数 t 的数组范围（缩小问题规模）来解决问题。

1、一开始，数组范围是整个原数组；
2、将目标数与数组的中位数比较，如果中位数大于目标数，则抛弃数组的后半部分，反之抛弃前半部分；
3、重复这个过程，直到找到目标数 t 或者数组范围为空为止。

例如，下图演示了在一组数据中查找目标数 7 的过程：

图片引用自维基百科

1.3 二分查找的优势

1、最省内存

二分查找算法基于已排序的原数组，属于本地查找算法。而基于二叉堆 / 散列表的查找算法还需要使用额外空间。

2、对数时间复杂度

二分查找的时间复杂度仅为 $O(lgn)$ 。

1.4 二分查找的局限性

1、依赖于顺序表

二分查找算法适用于顺序表，而不适用与链表。这是因为顺序表随机访问元素的时间复杂度为 $O(1)$ ，而链表随机访问的时间复杂度为 $O(n)$ ，后者实现二分查找的时间复杂度为 $O(nlgn)$ ，这比 $O(n)$ 顺序遍历链表还慢。

2、依赖于数据有序

二分查找的必要条件之一是数据有序，否则最低需要 $O(nlgn)$ 的时间复杂度进行预先排序（快速排序）。如果插入 / 删除操作不频繁，那么排序操作的时间成本可以被多次查找操作的成本均摊。这意味着二分查找适合静态有序的数据类型，或者插入 / 删除不频繁的动态数据数据。否则，应该采用二叉堆等动态数据类型。

3、不适用数据量太大的场景

二分查找依赖于顺序表，意味着存储数据就需要一块连续内存。如果程序的内存不足以分配这样一块连续的数组，那么就无法使用二分查找。

2. 二分查找解题框架

前面的内容相信大家很快就能理解了，我们直接看二分查找的原始题目 704 二分查找【题解】，并根据这个例子来讨论二分查找的解题框架。

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

2.1 解题框架三要素

二分查找解题框架由三个主要部分组成：

1、预处理

这个步骤主要处理特殊用例与数据预处理，对于特殊用例可以直接返回结果。而如果数据未排序，则先进行排序。排序过程一般使用快速排序，时间复杂度 $O(nlgn)$ ，空间复杂度 $O(1)$ 。

2、二分查找

主要思路是做 「排除法」，即：对于闭区间 $[left , right]$ ，每次观察中位数，根据中位数的值，把区间划分为两个区间：

一定不包含解的区间（抛弃）
可能包含解的区间

下一次遍历时，抛弃「一定不包含解的区间」，而在「可能包含解的区间」继续搜索。这里会存在两种写法，两种写法划分的区别是「区间范围是不一样」。

写法 1：尝试排除左区间

这种写法尝试判断「左区间」是否存在解，不存在则抛弃。此时， $[left , right]$ 应该划分为：

[left , mid - 1]
[mid , right]

当左区间存在解时，下次搜索区间就是 [left , mid - 1]
当左区间不存在解时，中位数却可能是解，所以下次搜索的区间需要覆盖 mid，即 [mid , right]

写法 2：尝试排除右区间

这种写法尝试判断「右区间」是否存在解，不存在则抛弃。此时， $[left , right]$ 应该划分为：

[left , mid]
[mid + 1, right]

当右区间存在解时，下次搜索区间就是 [mid + 1, right]
当右区间不存在解时，中位数却可能是解，所以下次搜索的区间需要覆盖 mid，即 [left , mid]

一定需要定义闭区间吗？

其实不是。其他一些解题模板定义了左闭右开的区间，不过这样反而增加了理解的难度。要知道一个左闭右开的区间 $[left , right)$ 一定存在一个等价的闭区间 $[left , right - 1]$ ，所以在我的模板里，就统一采用了闭区间啦。

3、后处理

在退出循环以后，只剩下 1 个数未检查，如果该元素满足条件则是目标解，否则题目无解。

2.2 解题框架

上一节所述题目参考代码如下：

参考代码 1：

fun search(nums: IntArray, target: Int): Int {
    if (nums.size == 0) {
        return -1
    }
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        写法 1：尝试排除左区间
        val mid = (left + right) ushr 1
        if (nums[mid] < target) {
            // [mid]严格小于目标值，不是解
            // 那么，下次搜索区间为[mid + 1,right]
            left = mid + 1
        } else {
            // [mid]可能是解
            // 那么，下次搜索区间为[left,mid]
            right = mid
        }
    }
    return if (nums[left] == target) left else -1
}

参考代码 2：

fun search(nums: IntArray, target: Int): Int {
    if (nums.size == 0) {
        return -1
    }
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        写法 2：尝试排除右区间
        val mid = (left + right + 1) ushr 1
        if (nums[mid] > target) {
            // [mid]严格大于目标值，不是解
            // 那么，下次搜索区间为[left,mid - 1]
            right = mid - 1
        } else {
            // [mid]可能是解
            // 那么，下次搜索区间为[mid,right]
            left = mid
        }
    }
    return if (nums[left] == target) left else -1
}

提示： 以上为 Kotlin 代码，Kotlin 中 shr 和 ushr 是移位运算，shr 是有符号右移，ushr 是无符号右移。

下面，我依次分析模板中需要注意的地方：

细节 1：left = 0，right = nums.size - 1

在 第 2.1 节 中，我们定义了问题为闭区间 $[left , right]$ ，因此 left 的初值为 0，而 right 的初始值为数组长度 - 1。这相对于其他一些解题模板 right = nums.size 更容易理解，因为我们 left 和 right 永远指向我们关心的区间。

细节 2：while(left < right)

表示二分查找的逻辑只处理区间长度大于 1 的情况，当区间只剩下一个元素的时候，退出循环执行后处理（如果最后一个元素满足条件则是目标解，否则，题目无解）。

细节 3：取中位数

取中位数的代码是mid = (left + right) / 2，这个写法是不严谨的。因为在 left 或 right 很大的时候，left + right 有可能发生溢出，所有较严谨的写法是：

mid = left + (right - left) / 2

另外，/ 2也可以用 移位操作 代替：

mid = (left + right) ushr 1

提示： 可以在 JDK Arrays.java 中看到类似的写法：
int mid = (low + high) >>> 1;

细节 4：区间的划分

在 第 2.1 节 中，我们介绍了二分查找的两种写法，要特别理解两种写法中区分的划分方法。

尝试排除左区间的写法：

[left , mid - 1] 尝试抛弃
[mid , right]

即：
left = mid
right = mid - 1

尝试排除右区间的写法：

[left , mid]
[mid + 1, right] 尝试抛弃

即：
left = mid + 1
right = mid

细节 5：向上取整与向下取整

当区间中含有奇数个元素时，中位数只有一个，例如，对于区间 $[1,2,3]$ ，中位数是 $2$ 。而当区间中含有偶数个元素时，中位数其实有两个。例如，对于区间 $[1,2,3,4]$ ，中位数是 $2$ 或者 $4$ 。

此时，取前一个中位数 $2$ 称为 向下取整，取后一个中位数 $4$ 称为 向上取整（奇数区间向上取整和向下取整是同一个数）:

向下取整：
(left + right) ushr 1
left + (right - left) / 2
向上取整：
(left + right + 1) ushr 1
left + (right - left + 1) / 2

那么，我们应该选择哪个中位数呢，选择不同中位数的结果一样吗？其实是不一样的。 这取决于我们在 细节 4 中采用的写法：

尝试排除左区间的写法：当搜索区间只剩下两个元素时，应该采用向上取整。

「反证法」：因为 $[left , right]$ 区间被划分为： $[left , mid - 1]$ 和 $[mid , right]$ ，如果选择向下取整（取前一个中位数，mid 的值等于 left），那么在左区间无法排除时，会进入left = mid的分支。此时，left 和 right 的值没有改变，出现区间不会缩小的情况，进入死循环。

尝试排除右区间的写法：当搜索区间只剩下两个元素时，应该采用向下取整。

「反证法」：因为 $[left , right]$ 区间被划分为： $[left , mid]$ 和 $[mid + 1 , right]$ ，如果选择向上取整（取后一个中位数，mid 的值等于 right），那么在右区间无法排除时，会进入right = mid的分支。此时，left 和 right 的值没有改变，出现区间不会缩小的情况，进入死循环。

细节 6：if (nums[left] == target) left else -1

执行后处理：在退出循环以后，只剩下 1 个数未检查，如果该元素满足条件则是目标解，否则题目无解。

3. 举一反三

让我们回顾前面讲的二分查找原始题目，你能找出题目中的关键词吗？题目中最关键的信息是：查找无重复升序数组中的目标数，即：

关键信息	描述
顺序表	必要条件
有序（或单调性）	必要条件
数据量不大	必要条件
无重复	/
一个目标数	/

其中，「无重复」和「一个目标数」不是必要条件，修改这两个因素可以延伸出更多题目。

提示： 有序数组的本质是数组值符合单调性，详见 第 3.5 节。

3.1 搜索满足条件的目标数

35. Search Insert Position 【题解】

69. Sqrt(x) 【题解】

162. Find Peak Element (Medium) 【题解】

287. Find the Duplicate Number

374. Guess Number Higher or Lower 【题解】

相对于【题 704 二分查找】，这类题最大的不同是目标数是「未知数」，要求我们找出这个目标数。这类题目的差不太大，我们要修正的只不过是排除区间的判断条件，使得下一次搜索的区间能够包含满足条件的目标数即可。

3.2 搜索目标数的边界

34. Find First and Last Position of Element in Sorted Array (Medium) 【题解】

相对于【题 704 二分查找】，这类题最大的不同是数组存在「重复」，要求我们找出目标数的开始位置和结束位置。我们依旧可以通过判断中位数与目标值的关系，来确定下一轮的搜索区间：

中位数严格小于目标数，那么一定不是开始位置
中位数严格大于目标数，那么一定不是结束位置

注意，比较容易出错的是：当我们找到一个与目标值相同的位置，再线性地向左和向右搜索目标值的边界，时间复杂度是 $O(n)$ ，而不再是 $O(lgn)$ 。

3.3 搜索旋转排序数组

33. Search in Rotated Sorted Array (Medium) 【题解】

81. Search in Rotated Sorted Array II (Medium) 【题解】

相对于【题 704 二分查找】，这类题最大的不同是数组是「旋转排序数组」，有序数组经过旋转后就不再是有序的，我们不能够直接对数组进行二分查找。但如果把数组看为左右两个有序数组拼接起来的，这两部分内部依旧是有序的，可以使用二分查找。所以我们的解题思路是：判断当前中位数是的位置：

位于左半部分：左边的元素严格有序，可以采用尝试抛弃左区间的写法
位于右半部分：右边的元素严格有序，可以采用尝试抛弃右区间的写法

两种写法的模板我们已经很熟悉了，但是需要注意到两种写法需要用到同一个中位数。而在前面的介绍中我们知道：抛弃左区间的写法使用前中位数，抛弃右区间的写法使用后中位数，该如何处理呢？其实我们可以观察到，在左半部分，区间 [left,mid] 是严格升序的，等于有 [left,mid - 1]也是升序的，所以可以直接使用 mid - 1 对应的前中位数。

更进一步，当数组中存在重复数字，如果中位数和左端点的数字相同，那么我们无法确定目标数是在左区间完全相同，还是右区间完全相同。此时，我们将 left++ 或者 right--，相当于去掉一个重复的干扰项。

图片引用自 LeetCode

153. Find Minimum in Rotated Sorted Array (Medium) 【题解】

154. Find Minimum in Rotated Sorted Array II (Hard) 【题解】

这道题不是寻找目标值，而是寻找旋转排序数组中的「最小值」。用排除法，我们要做的就是排除一定不存在最小值的区间：

位于左半部分：元素都比区间最后一个元素大，抛弃左区间
位于右半部分：中位数比区间最后一个元素大，抛弃右区间

更进一步，当数组中存在重复数组，如果中位数和左端点的数字相同，那么我们无法确定是分界点是在左区间还是右区间。与上一个问题类似，我们依旧可以将 left++ 或者 right--，从而减少一个重复的干扰项。

3.4 搜索山脉数组

1095. Find in Mountain Array (Hard) 【题解】

这道题与搜索旋转排序数组类似的地方在于：原数组整体是无序的，但组成数组的两部分内部是有序的。不同之处在于：搜索旋转排序数组可以通过比较中位数的值与的关系来判断当前所处的区间，但是山脉数组不再成立。

所以我们需要先找到山脉数组的峰值，再分别在两个区间内搜索目标值。

3.5 最大值极小化

410. Split Array Largest Sum 【题解】

875. Koko Eating Bananas 【题解】

1300. Sum of Mutated Array Closest to Target 【题解】

1482. Minimum Number of Days to Make m Bouquets 【题解】

1552. Magnetic Force Between Two Balls

LCP 12. 小张刷题计划 【题解】

这类问题也许是二分查找问题中最难的，相对于【题 704 二分查找】，这类题最大的不同是「没有明显的排序数组」「没有明显的目标数的条件」，灵活性非常大，对于没有经验的同学会很难联想到二分查找算法。

对于这类题目，最重要的点是挖掘题目中隐含的「单调性」。在前面的题目中大多用到「排序数组」，其实排序数组就隐含了一种单调性，即随着下标 x 的增大，数组值单调递增或者单调递减。

单调性

单调性（monotonicity）也可以叫做增减性，可以定性地描述两个变量之间的关系。当变量 $x$ 在其定义区间内增大时，函数 $y= f(x)$ 随着增大（或减小），则称函数 y 在该区间单调递增（或单调递减）。

【题 410. 木棍切割问题】是最大值最小化题目的经典问题：

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

当你看到 “最大值最小化” 类似的字样时，你应该想一想是不是可以用二分查找解决。那么，怎么挖掘题目中的两个变量之间的单调性呢？

这里有一个小套路：

1、分析题目中存在那几个变量；
2、找出题目中给出的某个固定值（例如此题的整数 m），这个固定值其实可以看作一个限制条件；
3、挖掘变量间的单调性：当变量 1 在区间内递增时，变量 2 单调递增或递减；
4、在变量 1 的区间内执行二分搜索，找出满足限制条件的最小值。

例如此题，经过分析可以看出题目中存在以下几个变量：

分割数 count
最大子数组和 maxSum

这两个变量的单调性是：当「最大子数组和」减小时，那么我们就需要多分割几次，「分割数」单调递增；而当「最大子数组和」增大时，那么我们就不需要划分那么多次了，「分割数」单调递减。

至于二分查找的步骤，我们要做的是在「最大子数组和」的取值区间内执行二分查找，找到分割数等于 m 的「目标数」。接下来就是编码啦，按照解题框架编写即可。

4. 总结

如果你也遇到二分查找算法一直写不对的问题，希望今天介绍的解题框架能对你有所启发。需要注意，一定要配合练习才能融会贯通，不要背解题框架。文章 第 3 节 整理了大量典型例题，应该能覆盖常见的题型，多去看看。最后，欢迎各位大佬们点赞、留言、转发。

参考资料

《二分查找词条》 —— 维基百科
《二分查找详解》 —— labuladong 著
《数据结构与算法之美》（第15、16课） —— 王争 jiang，极客时间出品
《用「排除法」（减治思想）写二分查找问题、与其它二分查找模板的比较》 —— liweiwei1419 著
《编程之法·面试和算法心得》（第4章） —— July 著
《编程珠玑》（第2、4、9章） —— [美] Jon Bentley 著

创作不易，你的「三连」是丑丑最大的动力，我们下次见！