第十六章：二分查找——快如闪电的查找方法¶
你好！欢迎来到第十六章！在前面的章节，我们学习了顺序查找——从第一个元素开始一个一个找，就像在一堆书里一本一本翻。但如果书已经按编号排好序了，我们还有更快的办法：先看中间那本，如果目标编号比中间的小，就去左边找；如果大，就去右边找。这样每次都能排除一半的书，这就是二分查找（也叫折半查找）。这一章我们就来学习这种高效的查找算法！
16.1 二分查找程序范例¶
假设我们有一个已经按升序排好的数组，要查找某个数是否在数组中，如果在，返回它的下标。
#include <iostream>
using namespace std;
// 二分查找函数，返回下标，没找到返回-1
int binarySearch(int arr[], int n, int target) {
int left = 0; // 查找范围的左边界
int right = n - 1; // 查找范围的右边界
while (left <= right) {
int mid = left + (right - left) / 2; // 中间位置，防止溢出
if (arr[mid] == target) {
return mid; // 找到了，返回下标
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分
} else {
right = mid - 1;// 目标在左半部分
}
}
return -1; // 没找到
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int target;
cout << "请输入要查找的数：";
cin >> target;
int pos = binarySearch(arr, n, target);
if (pos != -1) {
cout << "找到了，下标是：" << pos << endl;
} else {
cout << "没找到" << endl;
}
return 0;
}
运行示例（输入7）：
请输入要查找的数：7
找到了，下标是：3
运行示例（输入6）：
请输入要查找的数：6
没找到
16.2 二分查找的用法¶
16.2.1 二分查找的思想¶
二分查找就像猜数字游戏：对方想一个1-100之间的数，你每次猜中间的数，对方告诉你“大了”或“小了”，你就能排除一半的数字。这样最多猜7次就能猜到（因为2^7=128>100）。这就是二分查找的核心：每次把查找范围缩小一半。
适用条件：数组必须是有序的（升序或降序）。如果数组无序，必须先排序才能用二分查找。
16.2.2 二分查找的步骤¶
- 确定查找范围的左边界
left和右边界right（通常初始为0和n-1）。 - 当
left <= right时：
- 计算中间位置mid = left + (right - left) / 2。
- 如果arr[mid] == target，找到，返回mid。
- 如果arr[mid] < target，说明目标在右半部分，更新left = mid + 1。
- 如果arr[mid] > target，说明目标在左半部分，更新right = mid - 1。 - 如果循环结束还没找到，返回-1。
16.2.3 二分查找的代码实现¶
我们已经看到了迭代版本。也可以用递归实现：
int binarySearchRecursive(int arr[], int left, int right, int target) {
if (left > right) return -1; // 没找到
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, mid + 1, right, target);
} else {
return binarySearchRecursive(arr, left, mid - 1, target);
}
}
调用时：binarySearchRecursive(arr, 0, n-1, target);
16.2.4 注意事项¶
- 计算mid：用
left + (right - left) / 2而不是(left + right) / 2，防止left+right太大导致溢出。 - 边界条件：循环条件
left <= right要小心，如果写成<可能漏掉最后一个元素。 - 数组必须有序：如果数组无序，结果不可预测。
16.2.5 二分查找的变种¶
有时候我们需要找的不是精确等于某个值的下标，而是满足某种条件的边界。比如：
- 找第一个等于target的位置
- 找最后一个等于target的位置
- 找第一个大于等于target的位置
- 找最后一个小于等于target的位置
这些变种在STL中对应 lower_bound 和 upper_bound，我们也可以自己实现。
16.3 编程实例讲解¶
实例1：找第一个等于target的位置¶
当数组中有重复元素时，我们要找第一次出现的位置。
int firstOccurrence(int arr[], int n, int target) {
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid; // 记录找到的位置
right = mid - 1; // 继续在左边找
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
实例2：找最后一个等于target的位置¶
int lastOccurrence(int arr[], int n, int target) {
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
left = mid + 1; // 继续在右边找
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
实例3：找第一个大于等于target的位置（即 lower_bound）¶
int lowerBound(int arr[], int n, int target) {
int left = 0, right = n - 1;
int result = n; // 如果所有数都小于target，返回n（表示不存在）
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
实例4：在一个旋转有序数组中查找（选做）¶
题目：一个升序数组在某个点被旋转了，比如 [4,5,6,7,0,1,2]，在这个数组中查找某个数。
思路：先判断哪一半是有序的，然后根据target是否在有序部分来缩小范围。
int searchRotated(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
// 左半部分有序
if (arr[left] <= arr[mid]) {
if (target >= arr[left] && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 右半部分有序
else {
if (target > arr[mid] && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
16.4 阶段性编程练习¶
- 练习1：在有序数组 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 中查找数字 23 和 50，分别输出结果。
- 练习2：编写一个函数，用二分查找求一个数的平方根（整数部分）。例如输入10，返回3（因为3²=9≤10，4²=16>10）。提示：在0到x之间二分查找。
- 练习3：在一个有序数组中，找第一个大于 target 的位置（即 upper_bound）。
- 练习4：在一个有序数组中，统计某个数出现的次数（可以用 firstOccurrence 和 lastOccurrence 计算）。
- 练习5：用递归实现二分查找，并在主函数中测试。
16.5 第16章编程作业¶
作业1：查找插入位置¶
给定一个有序数组和一个目标值，如果目标值在数组中，返回其下标；如果不在，返回它应该插入的位置（保持有序）。例如数组 [1,3,5,6]，目标2，应返回1（插入在1和3之间）。
作业2：寻找峰值¶
在一个数组中，峰值是指该元素大于相邻元素（数组边界视为负无穷）。假设相邻元素不等，用二分查找找出任意一个峰值。例如 [1,2,1,3,5,6,4]，峰值可能是2或6。提示：比较中间元素与右边元素，如果中间小于右边，则峰值在右边，否则在左边。
作业3：在二维矩阵中查找¶
有一个 m×n 的矩阵，每行从左到右递增，每列从上到下递增。编写一个高效的算法查找某个数是否存在。提示：从右上角开始，类似二分。
作业4：两个有序数组的中位数¶
给定两个有序数组，找出它们的中位数。要求时间复杂度 O(log(min(m,n)))。这是一个经典难题，但可以尝试。
作业5：寻找重复数¶
给定一个包含 n+1 个整数的数组，每个整数都在 1 到 n 之间，所以至少有一个重复。找出这个重复的数，要求不修改数组且只用O(1)额外空间。可以用二分查找思想（值域二分）。
恭喜你完成了第十六章的学习！二分查找是一种非常高效的算法，它体现了“分而治之”的思想。在实际编程中，只要遇到有序数组的查找问题，就可以考虑二分查找。加油！🚀