引言

Donald E.Knuth 在《计算机程序设计艺术》的第 3 卷《排序和查找》中说到：“尽管第一个二分查找算法于 1946 年出现，然而第一个完全正确的二分查找算法实现直到 1962 年才出现。”

二分查找算法的最基础应用场景：在无重复元素的有序数组中，查找目标值的元素。这种场景的代码实现确实比较简单。但是，二分查找算法的变形问题可就不那么简单了。

比如，在有重复元素的有序数组中，查找第一个值等于目标值的元素、查找最后一个值等于目标值的元素、查找第一个大于等于目标值的元素、查找最后一个小于等于目标值的元素。你可以先自己试试看能否解决这些问题。

二分查找算法经常出现在大厂面试中的手撕环节，考察过该题目的公司有：拼多多、美团、腾讯、阿里巴巴、百度、华为等大厂。

我相信，友好的讨论交流会让彼此快速进步！文章难免有疏漏之处，十分欢迎大家在评论区中批评指正。

读完本篇文章，你将能轻松解决如下问题：

二分查找(力扣704)
如何用最省内存的方式实现千万级数据的快速查找？
在排序数组中查找元素的第一个和最后一个位置(力扣34)
在排序数组中查找数字I(剑指Offer53-I)
如何快速定位出一个 IP 地址归属地？
展厅如何限制入场人数？
搜索旋转排序数组（力扣33）

为了照顾完全不了解二分查找算法的新同学，文章将从最基本的二分查找算法讲起，探讨四种变体问题，给出两个实际应用问题，最后给出几个难易程度不同的算法问题用于练习。

查找一个数（基础用法）

具体描述

在无重复元素的有序数组中查找一个数，如果存在，返回其索引，否则返回 -1。

举个例子🌰

我们举一个例子，一个有序数组 nums，元素值分别是 [8, 10, 12, 16, 20]，我们想要找到目标值 target 为 10。我们如何使用二分搜索来做呢？

因为数组是有序的，我们每次取查找区间 [left, right] 中点的元素值与目标值比大小。

如图所示，left 是查找区间的左边界，right 是查找区间的右边界，红色方格为答案，应返回其索引 1。

下面，我来解释一下图中的流程：

nums[mid] > target，中点值大于目标值，说明中点值右边的值都比目标值大，因此目标值一定在左半区间 [left, mid - 1]。right 要左移，即 right = mid - 1，right 将指向索引 1 ，mid 将指向索引 0。
nums[mid] < target，中点值小于目标值，说明中点值左边的值都比目标值小，因此目标值一定在右半区间 [mid + 1, right]。left 要右移，即 left = mid + 1，left 将指向索引 1，mid 也将指向索引 1。
nums[mid] == target，找到目标值，直接返回 mid 索引为 1。

图中没有演示的一种情况是，如果遍历完整个数组后都没找到目标值，那就说明没找到，返回 -1。

参考代码

int binarySearch(int[] nums, int target) {
    // 查找区间 [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) { 
        // 计算 mid，详解见下方注解
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) { // 找到目标值，返回索引
            return mid;
        } else if (nums[mid] < target) { // 查找区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target){ // 查找区间变为 [left, mid-1]
            right = mid - 1;
        }
    }
    return -1;
}

为了清楚地展示所有细节，我将区间移动的所有情况都用 else if 写明，如果是第一次接触二分查找的同学，建议和我一样写清楚哦。

Tips!

有同学可能会有疑问，为什么计算 mid 不是使用 mid = (left + right) / 2 呢？

这是因为 mid = (left + right) / 2 有溢出的风险，如果 left 和 right 的值都特别大的话，两者相加就可能溢出。

改进的方法就是使用 mid = left + (right - left) / 2，更进一步的改进，从性能的角度考虑，位运算比除法更快，除以 2 的运算与位运算 >> 1 是等价的，因此最终写成 mid = left + ((right - left) >> 1)。

梳理细节

1. 查找区间：[left, right]，因为 right 初始化时是 nums.length - 1，即最后一个元素的索引。

2. 停止查找的条件：nums[mid] == target，找到目标值即停止。如果没有找到，while 循环终止，并返回 -1。

3. 循环终止条件：while (left <= right) 的循环终止条件是 left == right + 1 时，写成区间形式就是 [right + 1, right]，此时查找区间为空，说明不存在目标元素，直接返回 -1 即可。

4. 区间移动： 在查找区间为 [left, right] 时，若索引 mid 上的元素不是要找的 target 时，要去 [left, mid - 1] 或 [mid + 1, right] 区间上搜索，因为 mid 已经被搜索过了，应当从搜索区间中删除。

时间复杂度

$O(logn)$

对长度为 n 的数组进行二分，每次查找后数据量都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

被查找区间的大小变化为： $n$ ， $n/2$ ， $n/4$ ，...， $n/2^k$ ，这是一个等比数列，当 $n/2^k = 1$ 时， $k$ 的值就是缩小区间的次数，每一次缩小操作只涉及中点元素和目标值的大小比较，所以，经过了 $k$ 次区间缩小操作，时间复杂度就是 $O(k)$ ，而 $k = log_2n$ ，所以时间复杂度为 $O(logn)$ 。

O(logn) 是对数时间复杂度，这种复杂度十分高效。试想一下，如果二分查找 32 次，可以查找多长的有序数组中的目标值？ $2^{32} = 4,294,967,296$ ，在 42 亿多的数据量中，只需查找 32 次就能确定目标值的索引，是不是很惊人，是不是很大胆！

算法局限性

1. 二分查找只能在顺序表结构中，也就是数组。

二分查找需要数据结构支持下标随机访问元素。因此，链表这样的结构是不可以的，数组按照下标随机访问元素的时间复杂度是 O(1)，而链表随机访问元素的时间复杂度是 O(n)，因此如果使用链表来存储数据，再使用二分查找，那么时间复杂度就会特别高。

2. 二分查找要求数据必须有序。

二分查找适用于插入、删除不频繁，一次排序后多次查找的场景中。如果数据集合的数据经常发生变动，想要使用二分查找，就必须维护数据集合的有序性，这个维护成本非常高。

3. 数据量过大不适合二分查找。

诶嘿，是不是觉得很新奇，不是说数据量越大，二分查找的优越性越大吗？这就不得不提数组这个数据结构了。

二分查找底层依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间必须连续。比如，我们有 1GB 大小的数据，如果希望用数组来存储，那么就需要 1GB 的连续内存空间。

注意「连续」内存空间，如果你有 2GB 内存空间剩余，但是这些空间都是零散的，没有连续的 1GB 大小内存空间，那照样无法申请 1GB 大小的数组。而我们的二分查找是需要数组来支撑的。因此，如果数据量多到无法用数组来存储，那就无法使用二分查找了！

🔥如何用最省内存的方式实现千万级数据的快速查找？

情景描述

假设我们有 1000 万个整数数据，每个数据占 8 字节，最大内存空间占用不得超过 100MB。请你设计一种数据结构和算法，可以快速查找某个整数在这 1000 万的数据中的索引？

实现方案

我们可以将所有数据存储在数组中，然后将这些整数数据进行排序，再利用二分查找算法就可以快速查找想要的数据了。

我们要确定一下是否超出了内存限制，首先数据占用了约 78MB （ $10,000,000 \times 8B \div 1024 = 78.125 MB$ ）的空间，数组这种结构除了存储数据本身之外，不需要额外存储其他信息，因此符合内存限制。

我们知道散列表、二叉树也是支持快速查找的，大部分情况下，二分查找可以解决的问题，它们俩都可以解决。但是，这道题不行，因为这两种结构存储 1000 万的数据，100MB 内存肯定存不下。而二分查找底层依赖的数组，除了存储数据本身之外，不需要额外存储其他信息，是最省内存空间的存储方式，所以刚好能在限定的内存大小下解决这个问题。

查找第一个等于目标值的元素（变体1）

具体描述

在一个有序数组中，存在多个大小为 target 值的元素，请找到第一个等于目标值的元素（可以看作所有重复元素的左边界），如果存在，返回其索引，否则返回 -1。

举个例子🌰

俗话说，万变不离其宗。这道变体的解决思路和基础用法的思路是一致的，只不过在一些细节之处发生了变化。我们还是从一个例子入手。

我们以有序数组 [1, 3, 4, 5, 5, 5, 5, 5, 9]，目标值 target 为 5 为例进行讲解。

如图所示，left 是查找区间的左边界，right 是查找区间的右边界，红色方格为答案，应返回其索引 3。

nums[mid] == target，一开始我们就在数组中找到了和 target 相等的元素，可以直接返回索引 4 吗？

当然不可以啦，我们要找的是第一个 5，应该返回索引 3 才对。我们此时可以确定的是，答案一定在 [left, mid - 1] 这个查找区间中。因此，我们要左移右指针，right = mid - 1，左移后 right 将指向索引 3，mid 将指向索引 1。
nums[mid] < target，和基础二分搜索思路一样，此时应当右移 left，left = mid + 1，右移后，left 将指向索引 2，mid 也将指向索引 2。
nums[mid] < target，继续右移 left，left 将指向索引 3，mid 也将指向索引 3。
nums[mid] == target，此时就是我们想要找的答案，因为前面没有再等于 5 的啦。

Tips!

因为是有序数组，所以相同的元素都会连在一起。

所以，和上一个问题不同的地方就是，与目标值相等时，不能直接返回索引，而是要继续收缩查找区间，也就是左移右指针，从而锁定第一个等于目标值的元素。

参考代码

int searchFirstOne(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            // 如果此时 mid 是数组的第一个元素
            // 或者前面一个元素不等于目标值
            // 那么，这个元素就是答案，返回索引 mid
            if (mid == 0 || nums[mid - 1] != target)
                return mid;
            else
                // 答案一定出现在 mid 前面
            	right = mid - 1; // 缩小查找区间，左移右指针
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

答疑解惑

为什么能够查找到第一个等于目标值的元素？

关键点在于 nums[mid] == target 时的处理。

if (nums[mid] == target) {
    if (mid == 0 || nums[mid - 1] != target)
        return mid;
    else
	    right = mid - 1; // 缩小查找区间，左移右指针
}

当 nums[mid] 等于目标值 target 时，如果 mid 是数组的第一个元素，或者前面一个元素不等于 target 话，那么 nums[mid] 就是我们要找的元素，返回索引 mid。

如果此时， nums[mid] 前面一个元素 nums[mid - 1] 也等于 target，那说明，此时的 nums[mid] 肯定不是我们要找的第一个等于目标值的元素，所以，我们要左移右指针来缩小查找区间，在区间 [left, mid - 1] 中继续查找，也就是不断向左靠拢，这样一定能找到第一个等于目标值的元素。

其实，我在另一篇文章中，有写过该算法的另一种实现方法，更加简洁优雅，但是却不是那么容易理解，而且，无法完全解决今天的四个问题。

int searchFirstOne(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            right = mid - 1; // 缩小查找区间，左移右指针
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

虽然更优雅，但是理解难度比参考代码中的更难。

如果是你的话，你是想要更优雅但不容易理解的代码？还是没那么优雅但容易理解的代码呢？如果是我的话，我选择后者。

查找最后一个等于目标值的元素（变体2）

具体描述

在一个有序数组中，存在多个大小为 target 值的元素，请找到最后一个等于目标值的元素（可以看作所有重复元素的右边界），如果存在，返回其索引，否则返回 -1。

举个例子🌰

和查找第一个等于目标值的元素相反，找到目标值的时候，右移左指针，最终返回右指针索引即可。

所以，在上个问题的例子，有序数组 [1, 3, 4, 5, 5, 5, 5, 5, 9]，目标值 target 为 5，应当返回索引 7。

参考代码

int searchLastOne(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            // 如果此时 mid 是数组的最后一个元素
            // 或者后面一个元素不等于目标值
            // 那么，这个元素就是答案，返回索引 mid
            if (mid == nums.length - 1 || nums[mid + 1] != target)
                return mid;
            else
                // 答案一定出现在 mid 后面
            	left = mid + 1; // 缩小查找区间，右移左指针
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

答疑解惑

为什么能够查找到最后一个等于目标值的元素？

关键点在于 nums[mid] == target 时的处理。

if (nums[mid] == target) {
    if (mid == nums.length - 1 || nums[mid + 1] != target)
        return mid;
    else
	    left = mid + 1; // 缩小查找区间，右移左指针
}

当 nums[mid] 等于目标值 target 时，如果 mid 是数组最后一个索引，或者后面一个元素 nums[mid + 1] 不等于 target ，那么，nums[mid] 就是我们要找的元素，直接返回索引 mid。

如果此时， nums[mid] 后面的一个元素，nums[mid + 1] 也等于 target 话，那就说明当前的 nums[mid] 一定不是最后一个等于给定值的元素。所以，我们要右移左指针来缩小查找区间，在区间 [mid + 1, right] 中继续查找，也就是不断向右靠拢，这样一定能找到最后一个等于目标值的元素。

查找第一个大于等于目标值的元素（变体3）

具体描述

在任意有序数组中，查找第一个大于等于目标值的元素。如果存在，返回目标值索引，否则返回 -1。

举个例子🌰

继续使用之前的例子，有序数组 [1, 3, 4, 5, 5, 5, 5, 5, 9]，目标值 target 为 2，应该返回索引 1。

参考代码

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) {
            // 如果此时 mid 是数组的第一个元素
            // 或者前面一个元素比目标值小
            // 那么，这个元素就是答案，返回索引 mid
            if (mid == 0 || nums[mid - 1] < target) 
                return mid;
            else
                right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}

答疑解惑

为什么能够查找到第一个大于等于目标值的元素？

关键点在于 nums[mid] >= target 时的处理。

if (nums[mid] >= target) {
    if (mid == 0 || nums[mid - 1] < target)
        return mid;
    else
	    right = mid - 1; // 缩小查找区间，左移右指针
}

当 nums[mid] 大于等于 target 目标值时，如果 mid 是数组的第一个元素，或者前面一个元素小于 target ，那么，nums[mid] 一定是我们要找的元素，返回索引 mid。

如果此时，nums[mid] 前面一个元素 nums[mid] 也大于等于我们要查找的目标值，那说明，此时的 nums[mid] 肯定不是我们要找的第一个大于等于目标值的元素。所以，我们要左移右指针来缩小查找区间，在区间 [left, mid - 1] 中继续查找，也就是不断向左靠拢，这样一定能找到第一个大于等于目标值的元素。

查找最后一个小于等于目标值的元素（变体4）

具体描述

在任意有序数组中，查找最后一个小于等于目标值的元素。如果存在，返回目标值索引，否则返回 -1。

举个例子🌰

继续使用之前的例子，有序数组 [1, 3, 4, 5, 5, 5, 5, 5, 9]，目标值 target 为 6，应该返回索引 7。

参考代码

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] <= target) {
            if (mid == nums.length - 1 || nums[mid + 1] > target)
                return mid;
            else
                left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

答疑解惑

为什么能够查找到最后一个小于等于目标值的元素？

关键点在于 nums[mid] <= target 时的处理。

if (nums[mid] <= target) {
    if (mid == nums.length - 1 || nums[mid + 1] > target)
        return mid;
    else
	    left = mid + 1; // 缩小查找区间，右移左指针
}

当 nums[mid] 小于等于目标值 target 时，如果 mid 是数组最后一个索引，或者后面一个元素 nums[mid + 1] 不等于 target ，那么，nums[mid] 就是我们要找的元素，直接返回索引 mid。

如果此时， nums[mid] 后面的一个元素，nums[mid + 1] 也大于 target 话，那就说明当前的 nums[mid] 一定不是最后一个小于等于给定值的元素。所以，我们要右移左指针来缩小查找区间，在区间 [mid + 1, right] 中继续查找，也就是不断向右靠拢，这样一定能找到最后一个小于等于目标值的元素。

🔥如何快速定位出一个 IP 地址归属地？

情景描述

我们在浏览器搜索框中输入自己的 IP 地址，然后上面会显示它的归属地。

假设，我们查询 202.102.133.13 这个 IP 地址，其归属地属于山东省东营市，那具体是如何做到的呢？

我们需要再地址库中搜索 202.102.133.13 这个 IP 地址，发现这个 IP 地址落在 [202.102.133.0, 202.102.133.255] 这个地址范围内，那我们就可以将这个 IP 地址范围对应的归属地「山东省东营市」显示给用户即可。

[202.102.133.0, 202.102.133.255]  山东东营市 
[202.102.135.0, 202.102.136.255]  山东烟台 
[202.102.156.34, 202.102.157.255] 山东青岛 
[202.102.48.0, 202.102.48.255] 江苏宿迁 
[202.102.49.15, 202.102.51.251] 江苏泰州 
[202.102.56.0, 202.102.56.255] 江苏连云港

如果在庞大的 IP 地址库中逐个比对 IP 地址所在的区间，是非常耗时的。假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个 IP 地址的归属地呢？

实现方案

如果 IP 地址区间与归属地的对应关系不经常更新，我们可以预处理这 12 万条数据，让其按照起始 IP 从小到大排序。

如何来排序呢？IP 地址是可以转化成 32 为的整型数。所以我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。

然后，这个问题就可以转化为上面的变体 4 问题「查找最后一个小于等于目标值的元素」了。

当我们要查询某个 IP 归属地时，我们可以先通过二分查找，在起始地址中，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间。然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。

实战一下

如果大家能看到这里，相信一定有所收获了！下面，我们去用所学的知识去解决一些算法问题。建议先点开链接自己先做一遍，然后再看我给出的答案哦！

二分查找(力扣704)

题目描述

参考代码

直接套用「查找一个数」的代码就可以啦！

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

时间复杂度

$O(logN)$ ，N 是数组长度。

空间复杂度

$O(1)$ ，除了使用了常数个变量，没有额外的空间开销。

在排序数组中查找元素的第一个和最后一个位置(力扣34)

题目描述

参考代码

题目要求我们找到目标值在数组中的开始位置和结束位置，所谓的目标值在数组中的开始位置就是「查找第一个等于目标值的元素」，那么同理，在数组中的结束位置就是「查找最后一个等于目标值的元素」，这样就直接解决啦。

public int[] searchRange(int[] nums, int target) {
    return new int[] {searchFirstOne(nums, target), searchLastOne(nums, target)};
}  

int searchFirstOne(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            if (mid == 0 || nums[mid - 1] != target)
                return mid;
            else
	            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
} 

int searchLastOne(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            if (mid == nums.length - 1 || nums[mid + 1] != target)
                return mid;
            else
	            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

时间复杂度

$O(logN)$ ，N 是数组长度。

空间复杂度

$O(1)$ ，除了使用了常数个变量，没有额外的空间开销。

在排序数组中查找数字I(剑指Offer53-I)

题目描述

参考代码

这道题和上一道题整体思路是一样的，只不过最终我们要计算一下第一个和最后一个的区间内元素的个数。

public int search(int[] nums, int target) {
    int L = searchFirstOne(nums, target);
    int R = searchLastOne(nums, target);
    if ( L == -1 || R == -1) {
        return 0;
    } else {
        return R - L + 1;
    }
}

int searchFirstOne(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            if (mid == 0 || nums[mid - 1] != target)
                return mid;
            else
	            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int searchLastOne(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            if (mid == nums.length - 1 || nums[mid + 1] != target)
                return mid;
            else
	            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

时间复杂度

$O(logN)$ ，N 是数组长度。

空间复杂度

$O(1)$ ，除了使用了常数个变量，没有额外的空间开销。

🔥展厅如何限制入场人数？

题目描述

MWCS展共有 N 个展厅，每个展厅的报名人数记于数 nums，因疫情原因，所有展厅参展总人数上限为 cnt。若报名人数大于 cnt，则需要限制展厅入场的人数为 limit，根据输入，计算出 limit 最大值。

限制规则如下：

如果报名总人数少于 cnt，则全部可以入场，返回 -1；
如果报名总人数大于 cnt，则需要设定 limit。超过 limit 的报名人数的展厅，需要将入场人数限制为 limit；其余未达到 limit 的展厅的报名人，全部可以入场。

例 1：

输入: 

nums[] = [1,4,2,5,5,1,6]; // 每个展厅的报名人数
cnt = 13 // 总人数上限

输出：

2 // limit

例 2：

输入: 

nums[] = [1,1]; // 每个展厅的报名人数
cnt = 1 // 总人数上限

输出：

0 // limit

例 3：

输入: 

nums[] = [1,3,4,2]; // 每个展厅的报名人数
cnt = 195 // 总人数上限

输出：

-1 // limit

参考代码

这道题稍稍有难度了，我们看看二分查找如何在这道题里应用。

public int getMaxLimit(int[] nums, int cnt) {
    int sum = 0, max = 0;
    // 计算输入的展厅总人数 sum
    // 计算所有展厅中最大的入场人数 max
    for (int n : nums) {
        sum += n;
        max = Math.max(max, n);
    }
    // 如果报名总人数少于 cnt，则全部可以入场，返回 -1；
    if (sum <= cnt) {
        return -1;
    }
    // 如果报名总人数大于 cnt，则需要设定 limit。
    // 超过 limit 的报名人数的展厅，需要将入场人数限制为 limit；
    // 其余未达到 limit 的展厅的报名人，全部可以入场。
    
    // limit 的取值范围一定在 [0, max] 之间，可以使用二分查找确定 limit 的值
    // 我们的目标是，计算 limit 之后展厅总入场人数 sum 最接近 cnt（最后一个小于等于 cnt 的值）
    int left = 0, right = max;
    while (left <= right) {
        int mid = left + ((right - left) >> 1); // mid 就是我们要求的 limit
        if (calSum(nums, mid) <= cnt) { // 传入当前的 limit，计算展厅进入总人数小于等于 cnt
            // 如果 limit 是最大的数，或者传入后面一个 limit 计算展厅进入总人数大于 cnt，当前 mid 一定是答案
            if (mid == max || calSum(nums, mid + 1) > cnt) {
                return mid;
            } else { // limit 小了，要向右靠拢，右移左指针，缩小查找区间为 [mid + 1, right]
                left = mid + 1;
            }
        } else { // 传入当前的 limit，计算展厅进入总人数大于 cnt 
            right = mid - 1; //  limit 大了，要向左靠拢，左移右指针，缩小查找区间为 [left, mid - 1]
        }
    }
    return -1;
}

// 计算传入 limit 后，展厅进入的总人数
public int calSum(int[] nums, int limit) {
    int sum = 0;
    for (int n : nums) {
        // 取 {原展厅进入人数, 限制人数} 中较小的一个
        sum += Math.min(n, limit);
    }
    return sum;
}

这道题是不是有点儿难度，主要难点有二，一是在于能否识别出要使用二分查找去解题，二是如何使用二分查找去解决。

我们来与「查找最后一个小于等于目标值的元素（变体 4）」做个对比。

	变体 4	本题
目标	查找数组中最后一个小于等于目标值的元素	找到最大的 `limit` （在一个升序数组中，越靠后数越大）使得数组的累加和 `calSum()` 小于等于 `cnt`（目标值）
区间移动条件	数组中点元素值与目标值比较大小	当前 `limit` 下的数组累加和 `calSum()` 与 `cnt` 比较大小
初始查找范围	$[0,\ nums.length - 1]$	$[0,\ max]$ ，`max` 是所有展厅中最大的入场人数，`limit` 一定不会超过这个值

相信这样对比一下，大家应该就明白啦。另外，我再详细解释一下这段代码。

if (calSum(nums, mid) <= cnt) {
    if (mid == max || calSum(nums, mid + 1) > cnt) {
        return mid;
    } else {
        left = mid + 1;
    }
}

这段代码保证了我们一定能找到最大的 limit 使得数组的累加和 calSum() 小于等于 cnt。

如果此时找到的 limit（就是 mid）满足数组累加和 calSum() 小于等于 cnt，同时呢，limit （就是 mid）又是最后一个值，或者后面一个 limit （就是 mid）使得数组累加和 calSum() 大于 cnt，那么，当前的 mid 就是我们要找到的值，直接返回。

如果此时，后面一个 limit（就是 mid）下的数组累加和 calSum() 也小于等于 cnt 的话，那么当前的 limit（就是 mid）一定不是最大的 limit。所以我们要右移左指针来缩小查找区间，在区间 $[mid + 1,\ right]$ 中继续查找，也就是不断向右靠拢，最终一定能找到最大的满足数组累加和 calSum() 小于等于 cnt 的 limit 值。

🔥搜索旋转排序数组（力扣33）

题目描述

参考代码

这道题因为发生了旋转，使得数组变成了局部有序的情况。还可以二分查找吗？当然可以！

如果将数组从中间分开，我们会发现在查找区间 $[left,\ right]$ 中一定有一边是有序的。图示可以看到 $[left,\ right]$ 是有序的。因此，我们在每次分割完毕后，一定要查看一下 $[left,\ mid]$ 和 $[mid + 1,\ right]$ 哪边是有序的，我们要去有序的那个区间去确定区间如何移动，因为我们能够根据有序的区间判断出 target 是否在这个区间内。

如果 $[left,\ mid]$ 是有序的，并且 target 的大小在 $[nums[left],\ nums[mid])$ 之间，那么我们就要左移右指针，将查找区间缩小至 $[left,\ mid - 1]$ 。否则要在 $[mid + 1,\ right]$ 中寻找。
如果 $[mid + 1,\ right]$ 是有序的，且 target 的大小在 $(nums[mid],\ nums[right]]$ 之间，我么我们就要右移左指针，将查找区间缩小至 $[mid + 1,\ right]$ 。否则在 $[left,\ mid]$ 中寻找。

图示的情况是输入数组 nums = [4, 5, 6, 7, 0, 1, 2]，target = 0。

nums[mid] != target， $[left,\ mid]$ 是有序的，target 不在 $[nums[left],\ nums[mid])$ 区间，右移左指针，将查找区间缩小至 $[mid + 1,\ right]$ 。left 将指向索引 4，mid 将指向索引 1。
nums[mid] != target， $[left,\ mid]$ 是有序的，target 在 $[nums[left],\ nums[mid])$ 区间，左移右指针，将查找区间缩小至 $[left,\ mid - 1]$ 。 right 将指向索引 4，mid 将指向索引 4。
nums[mid] == target，返回索引 mid。

public int search(int[] nums, int target) {
    int n = nums.length;
    // 判断边界条件
    if (n == 0) {
        return -1;
    }
    if (n == 1) {
        return nums[0] == target ? 0 : -1;
    }
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[left] <= nums[mid]) { // 左半边是有序的，[left, mid] 有序
            // 如果 target 在 [left, mid) 之间，左移右指针，缩小查找区间 
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else { // 否则右移左指针，缩小查找区间
                left = mid + 1;
            }
        } else { // 右半边是有序的，[mid + 1, right] 有序
            // 如果 target 在 (mid, right] 之间，右移左指针，缩小查找区间
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else { // 否则左移右指针，缩小查找区间 
                right = mid - 1;
            }
        }
    }
    return -1;
}

代码框架

根据前面所讲的内容，我们提炼出如下的二分查找框架。建议再次回看一下基础用法和四种变体的代码，相信你一定会惊呼，原来都是一个套路！

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // 查找区间是闭区间 [left, right]
    while (left <= right) { // 可以遍历 nums 数组中所有元素
        int mid = left + ((right - left) >> 1);
        // 有时可以和其他条件合并
        if (nums[mid] == target) {
            if (...直接返回 mid 需要达成的条件...)
                return mid;
            else
                ...根据题目，移动查找区间...
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1; 
}

总结

二分查找是一种针对有序数组的高效查找算法，时间复杂度为 $O(logn)$ 。

它的核心思想非常简单，和分治思想类似。每次都取查找区间的中间元素与目标值对比，然后收缩（折半）查找区间，直到找到要查找的元素，或者区间缩小至 0。

二分查找虽然看上去简单，但是代码很容易出错，尤其是在变体问题上，因此在写代码时务必考虑以下细节：循环退出条件、查找终止条件、区间左右边界更新方法、返回值的选择。

二分查找的性能十分优秀，但是应用场景比较有限。其底层依赖数组，并且数组中的数据必须是有序的。二分查找十分适合处理静态数据，也就是数据集合没有频繁的数据插入、删除操作。

大多数二分查找能解决的问题，更倾向于使用散列表或者二叉查找树去解决。即使二分查找在内存使用上更节省，但是内存资源特别紧缺的情况并不多见。那这意味着二分查找没什么用处了吗？当然不是。

基础用法「查找一个数」的二分查找确实不怎么会被使用，二分查找更适合用在「近似」查找问题，在这类问题上，二分查找的优势十分明显，比如那 4 个变体问题，用散列表、二叉查找树就比较难实现了。

十分建议朋友们学习完毕后手动实现一遍所有代码，这样才会真正地消化吸收。

希望以上内容对你有帮助，一起加油！

更新日志

更新日期	更新内容
2023.5.27	提炼了一套二分查找代码框架
2023.5.27	更换了文章主题：smartblue + github

参考资料

数据结构与算法之美
算法（第四版）
算法图解
牛客网
力扣网

8k+字！详细解读二分查找变体问题，与 bug 说再见！

引言

查找一个数（基础用法）

具体描述

举个例子🌰

参考代码

梳理细节

时间复杂度

算法局限性

🔥如何用最省内存的方式实现千万级数据的快速查找？

情景描述

实现方案

查找第一个等于目标值的元素（变体1）

具体描述

举个例子🌰

参考代码

答疑解惑

查找最后一个等于目标值的元素（变体2）

具体描述

举个例子🌰

参考代码

答疑解惑

查找第一个大于等于目标值的元素（变体3）

具体描述

举个例子🌰

参考代码

答疑解惑

查找最后一个小于等于目标值的元素（变体4）

具体描述

举个例子🌰

参考代码

答疑解惑

🔥如何快速定位出一个 IP 地址归属地？

情景描述

实现方案

实战一下

二分查找(力扣704)

题目描述

参考代码

时间复杂度

空间复杂度

在排序数组中查找元素的第一个和最后一个位置(力扣34)

题目描述

参考代码

时间复杂度

空间复杂度

在排序数组中查找数字I(剑指Offer53-I)

题目描述

参考代码

时间复杂度

空间复杂度

🔥展厅如何限制入场人数？

题目描述

参考代码

🔥搜索旋转排序数组（力扣33）

题目描述

参考代码

代码框架

总结

更新日志

参考资料