二分搜索（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 时，表示未找到目标值。二分搜索适用于以下场景：
以下是标准二分搜索的代码实现，在有序数组中查找目标值并返回其下标：
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 次比较后确定元素不存在。
遇到二分搜索相关问题时，需要特别注意不同变种的区别：
left <= right，找到即返回。nums[mid] == target 后不能立即返回，而是记录答案并继续在左半部分搜索（right = mid - 1）。left = mid + 1）。nums[mid] >= target 时，记录答案并搜索左半部分。nums[mid] <= target 时，记录答案并搜索右半部分。掌握这些变种是二分搜索的关键，建议逐个理解并练习。
(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。