本课时有配套视频讲解，购买后即可观看（永久有效）
二分搜索
一、课上练习
编程练习
二、知识总结
✨ 核心思想
二分搜索（Binary Search）是一种高效的搜索算法，用于在有序数组中查找特定元素。它通过逐步缩小查找范围来实现较低的时间复杂度，是最基础也最重要的算法之一。
二分搜索的核心特点：
- 前提条件：二分搜索只能在有序的数组或列表中使用
- 工作原理：通过比较目标值与中间元素的大小关系，决定在数组的哪一半中继续搜索，逐步缩小查找范围，直到找到目标元素或范围为空
- 效率高：与线性搜索相比，二分搜索的查找速度更快，特别是在处理大型数据集时
- 限制条件：要求数组是有序的。如果数据无序，需要先排序，这可能会增加额外的时间开销
✨ 算法原理
二分搜索的具体执行步骤如下：
- 初始化边界：设定两个指针，
left和right，分别指向数组的起始位置和结束位置。 - 计算中点：计算中点索引
mid，通常使用公式mid = left + (right - left) / 2以避免潜在的整数溢出。 - 比较中点值：
- 如果
a[mid]等于目标值target，则返回中点索引 - 如果
a[mid]小于target，则将left更新为mid + 1，继续在右半部分查找 - 如果
a[mid]大于target，则将right更新为mid - 1，继续在左半部分查找
- 如果
- 循环终止：当
left超过right时，表示未找到目标值。
✨ 算法评价
- 时间复杂度：O(log n)，每次操作都会将搜索范围缩小一半，因此即使面对百万级数据，也只需约 20 次比较即可完成查找。
- 空间复杂度：O(1)，只使用了常数级别的额外空间（迭代实现）。
✨ 应用场景
二分搜索适用于以下场景：
- 查找有序数据中的特定值
- 求解具有单调性问题（如最小化、最大化问题）
- 实现高效的动态数据结构（如平衡二叉搜索树中的操作）
✨ 代码实现
以下是标准二分搜索的代码实现，在有序数组中查找目标值并返回其下标：
二分搜索代码示例
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int binarySearch(const vector<int>& nums, int target) {
6 int left = 0;
7 int right = nums.size() - 1;
8
9 while (left <= right) {
10 int mid = left + (right - left) / 2;
11
12 if (nums[mid] == target) {
13 return mid; // 找到目标值，返回索引
14 } else if (nums[mid] < target) {
15 left = mid + 1; // 目标值在右半部分
16 } else {
17 right = mid - 1; // 目标值在左半部分
18 }
19 }
20
21 return -1; // 未找到目标值，返回-1
22}
23
24int main() {
25 vector<int> nums = {1, 3, 5, 7, 9, 11};
26 int target = 7;
27
28 int result = binarySearch(nums, target);
29 if (result != -1) {
30 cout << "Element found at index " << result << endl;
31 } else {
32 cout << "Element not found" << endl;
33 }
34
35 return 0;
36}✨ 执行示例
以在有序数组 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中查找 target=23 为例：
| 轮次 | left | right | mid | nums[mid] | 与target比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 23 | left = 4+1 = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 23 | right = 7-1 = 6 |
| 3 | 5 | 6 | 5 | 23 | 23 == 23 | 找到，返回 5 |
仅用 3 次比较就找到了目标值，而线性搜索需要 6 次。
再看一个查找不存在元素的例子：在同一数组中查找 target=20：
| 轮次 | left | right | mid | nums[mid] | 与target比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 20 | left = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 20 | right = 6 |
| 3 | 5 | 6 | 5 | 23 | 23 > 20 | right = 4 |
| 4 | left=5 > right=4 | - | - | - | 循环结束 | 返回 -1 |
4 次比较后确定元素不存在。
✨ 解题步骤详解
遇到二分搜索相关问题时，需要特别注意不同变种的区别：
- 标准二分搜索（查找精确值）：找到时返回下标，找不到返回 -1。循环条件
left <= right，找到即返回。 - 查找第一个等于 target 的位置：找到
nums[mid] == target后不能立即返回，而是记录答案并继续在左半部分搜索（right = mid - 1）。 - 查找最后一个等于 target 的位置：找到后记录答案并继续在右半部分搜索（
left = mid + 1）。 - 查找第一个大于等于 target 的位置：当
nums[mid] >= target时，记录答案并搜索左半部分。 - 查找最后一个小于等于 target 的位置：当
nums[mid] <= target时，记录答案并搜索右半部分。
掌握这些变种是二分搜索的关键，建议逐个理解并练习。
✨ 常见错误
- 数组未排序就使用二分搜索：二分搜索的前提是数组有序。如果数据无序，必须先排序。
- mid 计算溢出：
(left + right) / 2当 left 和 right 都很大时可能溢出。应使用left + (right - left) / 2。 - 边界更新错误：
left = mid或right = mid可能导致死循环（当left + 1 == right时 mid 始终等于 left）。正确做法通常是left = mid + 1或right = mid - 1。 - 循环条件搞混：
left <= right和left < right对应不同的二分写法，不能混用。用<=时，退出循环意味着left > right；用<时，退出循环意味着left == right。 - 变种写法中忘记记录答案：在查找"第一个"或"最后一个"等变种中，找到匹配后不能直接返回，需要先记录当前位置再继续缩小范围。