前言

二分查找也称折半查找（Binary Search），是一种效率较高的查找方法（对数时间复杂度），同时也是面试中经常考到的问题。虽然它的思想很简单，但据《编程珠玑》所述，二分查找算法的实现是极易犯错的。

1. 二分查找基础

1.1 问题描述

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

1.2 算法描述

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

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

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

图片引用自维基百科

1.3 二分查找的优势

1、最省内存

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

2、对数时间复杂度

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

1.4 二分查找的局限性

1、依赖于顺序表

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

2、依赖于数据有序

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

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

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

2. 二分查找解题框架

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

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
复制代码

1.1 解题框架三要素

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

1、预处理

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

2、二分查找

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

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

这里会存在两种写法，不同写法划分的区间范围是不一样的。

写法 1：尝试排除左区间

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

[left , mid - 1] 尝试抛弃
[mid , right]
复制代码

写法 2：尝试排除右区间

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

[left , mid]
[mid + 1, right] 尝试抛弃
复制代码

一定需要定义闭区间吗？

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

3、后处理

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

1.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

在 第 1.1 节 中，我们定义了问题为闭区间[left,right][left , right][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) shr 1
复制代码

提示： 可以在 JDK Arrays.java 中看到类似的写法：

int mid = (low + high) >>> 1;
复制代码

细节 4：区间的划分

在 第 1.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][1,2,3][1,2,3]，中位数是222。而当区间中含有偶数个元素时，中位数其实有两个。例如，对于区间[1,2,3,4][1,2,3,4][1,2,3,4]，中位数是222或者444。

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

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

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

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

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

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

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

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

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

3. 举一反三

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

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

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

3.1 搜索旋转排序数组

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

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

虽然旋转过的数组不是有序的，无法直接对数组进行二分查找。但如果把数组看为左右两部分的话，则这两部分依旧是有序的，可以使用二分查找。所以我们的解题思路是：判断当前中位数是的位置：

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

两种写法的模板我们已经很熟悉了，但是需要注意到两种写法需要用到同一个中位数。而在前面的介绍中我们知道：抛弃左区间的写法使用前中位数，抛弃右区间的写法使用后中位数，该如何处理呢？

可以观察到，在左半部分，区间 [left,mid] 是严格升序的，那么有 [left,mid - 1]也是升序的，所以可以直接使用 mid - 1 对应的前中位数。

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

【33.题解】

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        if (nums.isEmpty()) {
            return -1
        }
        var left = 0
        var right = nums.size - 1
        while (left < right) {
            val mid = (left + right + 1) ushr 1
            if (nums[0] < nums[mid]) {
                // 区间 [left,mid] 严格升序，尝试抛弃左区间
                // 有 [left,mid - 1] 也是升序的，所以可以直接使用 mid - 1 对应的前中位数
                val mid2 = mid - 1
                if (nums[mid2] < target || nums[0] > target) {
                    left = mid2 + 1 // 下次搜索[mid2,right]
                } else {
                    right = mid2 // 下次搜索[left,mid2]
                }
            } else {
                // 区间 [mid,right] 严格升序，尝试抛弃右区间
                if (nums[mid] > target || nums[nums.size - 1] < target) { // nums[0] < target 在 [3,1] 1 出错
                    right = mid - 1 // 下次搜索[left,mid-1]
                } else {
                    left = mid // 下次搜索[mid,right]
                }
            }
        }
        return if (nums[left] == target) left else -1
    }
}
复制代码

【81.题解】

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        if (nums.isEmpty()) {
            return -1
        }
        var left = 0
        var right = nums.size - 1
        while (left < right) {
            val mid = (left + right + 1) ushr 1
            // 因为数组存在重复数字，如果中点和左端的数字相同，我们并不能确定是左区间全部相同，还是右区间完全相同。
            // 此时，我们将 left++ ，相当于去掉一个重复的干扰项
            if(nums[left] == nums[mid]){
                left ++
                continue
            }
            if (nums[0] < nums[mid]) {
                // 区间 [left,mid] 严格升序，尝试抛弃左区间
                // 有 [left,mid - 1] 也是升序的，所以可以直接使用 mid - 1 对应的前中位数
                val mid2 = mid - 1
                if (nums[mid2] < target || nums[0] > target) {
                    left = mid2 + 1 // 下次搜索[mid2,right]
                } else {
                    right = mid2 // 下次搜索[left,mid2]
                }
            } else {
                // 区间 [mid,right] 严格升序，尝试抛弃右区间
                if (nums[mid] > target || nums[nums.size - 1] < target) { // nums[0] < target 在 [3,1] 1 出错
                    right = mid - 1 // 下次搜索[left,mid-1]
                } else {
                    left = mid // 下次搜索[mid,right]
                }
            }
        }
        return if (nums[left] == target) left else -1
    }
}
复制代码

3.2 搜索目标数的边界

Editting...

最大值最小化：丢鸡蛋

算法 | 一听就懂，一写就错，二分查找是送分题还是送命题？

前言

目录

1. 二分查找基础

1.1 问题描述

1.2 算法描述

1.3 二分查找的优势

1.4 二分查找的局限性

2. 二分查找解题框架

1.1 解题框架三要素

1.2 解题框架

3. 举一反三

3.1 搜索旋转排序数组

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

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

3.2 搜索目标数的边界

4. 总结

热门文章

最新文章

相关课程

相关电子书

相关实验场景