第 32 课：二分查找
蛙蛙路过一家电子产品专卖店，店长为了吸引顾客，推出了一个"猜价格赢优惠券"活动。刚好蛙蛙想要买一台平板电脑，于是他便准备参与这项活动。
蛙蛙挑选出一台平板电脑，店长告诉蛙蛙这个价格在 1000 元和 5000 元之间，且为整数。蛙蛙可以通过向店长提问来猜出这个价格，每次提问店长只能回答"是"或者"不是"，一共给蛙蛙 9 次机会。
如果通过枚举的方式去猜，肯定不行，那该怎么解决这个问题呢？于是他拨通了氪町博士的电话，氪町博士教给了他一种方法，叫作二分查找。
32.1 二分查找的概念
二分查找又称为折半查找，主要用于查找一个有序数组中某一个数的位置，它的主要思想如下：在一个有序数组中，取数组的中间值与要查找的数进行比较，若要查找的数等于中间值，查找成功。
查找步骤
以下表为例，其中 16 为中间值，从中间值 16 开始查找。
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 值 | 1 | 3 | 5 | 8 | 10 | 16 | 21 | 24 | 26 | 30 | 33 |
若要查找的数大于中间值（比如要查找的数是 24），则在右半区间（21 到 33）继续取中间值与要查找的数进行比较；
若要查找的数小于中间值（比如要查找的数是 8），则在左半区间（1 到 10）继续取中间值与要查找的数进行比较；
直至要查找的数等于中间值，查找成功，或者未出现过与中间值相等的情况，查找失败。
场景演示
了解完二分查找的方式后，蛙蛙对店长进行了折半提问，他先问："这个价格大于 3000 元吗？"店长回答："不是。"
于是蛙蛙将价格范围缩小到 1000 元和 3000 元之间。他接着问："这个价格大于 2000 元吗？"店长回答："是。"
这样蛙蛙又把范围缩小到 2000 元和 3000 元之间。他继续提问："这个价格大于 2500 元吗？"店长回答："是。"
范围进一步缩小到 2500 元和 3000 元之间，蛙蛙接着问："这个价格大于 2750 元吗？"店长回答："不是。"
此时蛙蛙知道价格在 2500 元和 2750 元之间，他又问："这个价格大于 2625 元吗？"店长回答："是。"
最后蛙蛙再问："这个价格是 2688 元吗？"店长笑着回答："是！恭喜你猜对了！"
蛙蛙通过不断运用二分查找的策略，每次将可能的价格范围缩小一半，最终成功猜出了平板电脑的价格，赢得了一张价值 500 元的购物优惠券。
32.2 二分查找的操作
定义 Search 函数表示二分查找算法并引入三个参数，这三个参数分别是数组、数组长度、查找值，返回的是查找值在数组中的位置。
int Search(int a[], int n, int key)
{
int low = 1; // 左边界从 1 开始
int high = n; // 右边界从 n 开始
while (low <= high)
{
int mid = low + ((high - low) / 2); // 中间下标
if (key == a[mid]) // 相等代表找到
return mid;
else if (key < a[mid]) // 比中间值小，把右边界缩小
high = mid - 1;
else // 比中间值大，把左边界缩小
low = mid + 1;
}
return -1;
}32.3 二分查找的优势
二分查找是一种高效的查找算法，相较于顺序查找等其他查找方法，具有以下显著优势。
时间复杂度低：二分查找的时间复杂度为 O(log n)，其中 n 是数据集合的元素个数，这意味着随着数据规模的增大，二分查找所需的时间增长非常缓慢。例如，对于一个包含 1000 个元素的有序数组，顺序查找最多需要 1000 次，而二分查找最多只需 10 次（因为 2¹⁰ = 1024）。
查找效率高：每次比较都能将搜索范围缩小一半，能够快速定位到目标元素或确定目标元素不存在。
空间复杂度低：二分查找只需要常数级别的额外空间，即 O(1) 的空间复杂度，它不需要额外的大量空间来存储数据或中间结果，只需要几个变量来记录查找的范围和中间元素的位置等信息。
32.4 实例讲解
例 1：查找某个数的位置
在一个有序数组中查找某个数，并输出这个数的下标。数组中不存在重复的值，若没有找到这个数，则返回 −1。
【输入格式】输入 n + 2 行。
第 1 行输入用空格隔开的两个整数，分别表示序列长度 n 以及查询次数 m。
第 2 行输入 n 个整数。
接下来 m 行，每行一个整数，表示查询的数。
【输出格式】输出 m 行，每行为查询数的位置（位置从 1 开始算）。
【输入样例】
3 3
4 6 9
9
4
7【输出样例】
3
1
-1【数据范围】
序列长度 n，满足 1 ≤ n ≤ 10⁵。
查询次数 m，满足 1 ≤ m ≤ 10³。
数组中的每个整数 aᵢ，满足 −10⁹ ≤ aᵢ ≤ 10⁹。
每次查询的数 x，满足 −10⁹ ≤ x ≤ 10⁹。
解析
样例分析
输入 4 6 9，输出 9。以下左边界为 low，右边界为 high，中间下标为 mid。
初始时，low = 1，high = 3，mid = (1 + 3) / 2 = 2，a[2] = 6。
因为 9 > 6，所以更新 low = mid + 1 = 3。
此时，low = 3，high = 3，mid = (3 + 3) / 2 = 3，a[3] = 9。
因为 9 == 9，所以返回 mid = 3。
参考代码
#include <iostream>
using namespace std;
int Search(int a[], int n, int key)
{
int low = 1;
int high = n;
while (low <= high)
{
int mid = low + ((high - low) / 2);
if (key == a[mid])
return mid;
else if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main()
{
int s[100001], n, m, b;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= m; i++)
{
cin >> b;
cout << Search(s, n, b) << endl;
}
return 0;
}例 2：查找第一个比某数大的数
从一个有序的整数序列中查找第一个大于整数 x 的数，如果存在则输出该数出现位置，否则输出 −1。序列中有重复元素，并且单调递增。
【输入格式】输入 n + 2 行。
第 1 行输入用空格隔开的两个整数，分别表示序列长度 n 以及查询次数 m。
第 2 行输入 n 个整数。
接下来 m 行中，每行一个整数，表示查询的数。
【输出格式】输出 m 行，每行为查询数的位置（位置从 1 开始算）。
【输入样例】
5 3
2 2 3 3 5
3
2
6【输出样例】
5
3
-1【数据范围】
对于序列长度 n，满足 1 ≤ n ≤ 10⁵。
对于查询次数 m，满足 1 ≤ m ≤ 10³。
对于数组中的每个整数 aᵢ，满足 −10⁹ ≤ aᵢ ≤ 10⁹。
对于每次查询的数 x，满足 −10⁹ ≤ x ≤ 10⁹。
解析
初始化查找范围：由于位置从 1 开始计数，所以需要将左边界 low 初始化为 1，右边界 high 初始化为序列的长度 n，以此确定初始的查找范围。
二分查找循环
a. 只要 low 小于或等于 high，就持续进行查找操作。
b. 若查找值 key 小于中间位置的数，说明第一个大于 key 的数可能在左半部分，于是更新 high 为 mid - 1，缩小查找范围。
c. 若查找值 key 大于或等于中间位置的数，说明第一个大于 key 的数在右半部分，更新 low 为 mid + 1。
结果判断
a. 当循环结束后，若 low 小于或等于 n，表明找到了第一个大于 key 的数，其位置就是 low，返回 low。
b. 若 low 大于 n，意味着序列中不存在大于 key 的数，返回 −1。
参考代码
#include <iostream>
using namespace std;
int Search(int a[], int n, int key)
{
int low = 1;
int high = n;
while (low <= high)
{
int mid = low + ((high - low) / 2);
if (key < a[mid])
high = mid - 1;
else
low = mid + 1; // 包含相等的情况
}
if (low <= n)
return low; // 判断左边界是否超过最后一个数
else
return -1;
}
int main()
{
int s[100001], n, m, b;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= m; i++)
{
cin >> b;
cout << Search(s, n, b) << endl;
}
return 0;
}例 3：查找第一个大于或等于某数的位置
从一个有序的整数序列中查找第一个大于或等于整数 x 的数，如果存在，则输出出现位置，否则输出 −1。序列中有重复元素，并且单调递增。
【输入格式】输入 n + 2 行。
第 1 行输入以空格隔开的两个整数，分别表示序列长度 n 以及查询次数 m。
第 2 行输入 n 个整数。
接下来的 m 行中，每行一个整数，表示查询的数。
【输出格式】输出 m 行，每行为查询数的位置（位置从 1 开始算）。
【输入样例】
5 3
2 2 3 4 4
2
4
6【输出样例】
1
4
-1【数据范围】
对于序列长度 n，满足 1 ≤ n ≤ 10⁵。
对于查询次数 m，满足 1 ≤ m ≤ 10³。
对于数组中的每个整数 aᵢ，满足 −10⁹ ≤ aᵢ ≤ 10⁹。
对于每次查询的数 x，满足 −10⁹ ≤ x ≤ 10⁹。
解析
本题主要分析左右边界移动情况。
当 key < a[mid] 时：这种情况下，第一个大于或等于 key 的数肯定在当前中间位置 mid 的左边，所以要把右边界 high 移动到 mid - 1，以此缩小查找范围到左半部分。
当 key > a[mid] 时：此时，第一个大于或等于 key 的数必定在当前中间位置 mid 的右边，因此将左边界 low 移动到 mid + 1，把查找范围缩小到右半部分。
当 key == a[mid] 时：虽然当前的 a[mid] 已经满足大于或等于 key 的条件，但由于序列中存在重复元素，可能在 mid 左边还有等于 key 的元素。为了找到第一个大于或等于 key 的元素，也就是最左边的那个满足条件的元素，我们需要继续在左半部分查找，所以需要把右边界 high 移动到 mid - 1 的位置。
参考代码
#include <iostream>
using namespace std;
int Search(int a[], int n, int key)
{
int low = 1;
int high = n;
while (low <= high)
{
int mid = low + ((high - low) / 2);
if (key <= a[mid]) // 相等时移动右边界
high = mid - 1;
else
low = mid + 1;
}
if (low <= n)
return low;
else
return -1;
}
int main()
{
int s[100001], n, m, b;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= m; i++)
{
cin >> b;
cout << Search(s, n, b) << endl;
}
return 0;
}例 4：查找某数第一次出现的位置
从一个有序的整数序列中查找整数 x，如果存在，则输出第一次出现的位置，否则输出 −1。序列中有重复元素，并且单调递增。
【输入格式】输入 n + 2 行。
第 1 行输入以空格隔开的两个整数，分别表示序列长度 n 以及查询次数 m。
第 2 行输入 n 个整数。
接下来的 m 行中，每行输入一个整数，表示查询的数。
【输出格式】输出 m 行，每行为查询数的位置（位置从 1 开始算）。
【输入样例】
5 3
2 2 3 4 5
1
2
3【输出样例】
-1
2
1【数据范围】
对于序列长度 n，满足 1 ≤ n ≤ 10⁵。
对于查询次数 m，满足 1 ≤ m ≤ 10³。
对于数组中的每个整数 aᵢ，满足 −10⁹ ≤ aᵢ ≤ 10⁹。
对于每次查询的数 x，满足 −10⁹ ≤ x ≤ 10⁹。
解析
在上一题的基础上进行判断，只有当左指针 low 在数组范围内且 a[low] 等于 key 时，才能确定 low 就是目标元素 key 第一次出现的位置，此时返回 low；否则，返回 −1，表示没有找到目标元素。
参考代码
#include <iostream>
using namespace std;
int Search(int a[], int n, int key)
{
int low = 1;
int high = n;
while (low <= high)
{
int mid = low + ((high - low) / 2);
if (key <= a[mid])
high = mid - 1;
else
low = mid + 1;
}
if (low <= n && a[low] == key) // 增加条件
return low;
else
return -1;
}
int main()
{
int s[100001], n, m, b;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= m; i++)
{
cin >> b;
cout << Search(s, n, b) << endl;
}
return 0;
}