← 目录 / 算法文档 · 模块七 双指针与二分查找 / 7.2 二分查找

7.2　二分查找

每看一次中间的数，就能排除掉一半的范围——在有序数组里，这是查找的最快方式。

本页目录
① 什么是二分查找

想象在字典里查一个字——不会从第一页开始一页页翻，而是直接翻到中间，看看要找的字在前半部分还是后半部分，然后只在那一半里继续翻——每翻一次，能找的范围就缩小一半。二分查找就是把这个直觉写成算法：在一个已经排好序的数组里，每次检查中间的数，根据比较结果排除掉一半的范围，直到找到目标或者范围缩小到空为止。

② 基础写法：每次排除一半

用 left、right 维护当前还需要查找的范围。每一轮取中间下标 mid，比较 arr[mid] 和目标值：相等就直接返回；偏小说明目标在右半部分，把 left 移到 mid+1；偏大说明目标在左半部分，把 right 移到 mid-1。

C++ · 二分查找
1int BinarySearch(vector<int> arr, int target)
2{
3 int left = 0, right = arr.size() - 1;
4 while (left <= right)
5 {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target)
8 {
9 return mid;
10 }
11 else if (arr[mid] < target)
12 {
13 left = mid + 1; // 目标在右半部分
14 }
15 else
16 {
17 right = mid - 1; // 目标在左半部分
18 }
19 }
20 return -1; // 没找到
21}
⚠️
为什么写 mid = left + (right - left) / 2，不直接写 (left + right) / 2？这是为了防止溢出——如果 left 和 right 都已经是很大的数（接近 int 的上限），left + right 这一步加法本身就可能先溢出，哪怕最终算出来的 mid 没什么问题。left + (right - left) / 2 先算两者的差（不会比 right 本身大），再加回 left，全程不会经过比 right 更大的中间值，是更安全的写法——和 1.5 节最小公倍数公式"先除再乘"防止溢出是同一种思路。
{2,5,8,12,16,23,38,45,56,67,72}，target=45 —— 二分查找执行过程
第1轮：left=0, right=10, mid=5 → arr[5]=23，太小，往右找（left=6）
2
5
8
12
16
23
38
45
56
67
72
第2轮：left=6, right=10, mid=8 → arr[8]=56，太大，往左找（right=7）
2
5
8
12
16
23
38
45
56
67
72
第3轮：left=6, right=7, mid=6 → arr[6]=38，太小，往右找（left=7）
2
5
8
12
16
23
38
45
56
67
72
第4轮：left=7, right=7, mid=7 → arr[7]=45，找到！
2
5
8
12
16
23
38
45
56
67
72
灰色虚线格子是已经被排除、不可能再被访问到的区域。11 个数的数组，只用了 4 次比较就找到了目标——如果用最朴素的线性查找（从头一个个比对），最坏情况要比较 11 次。每一轮被排除的区域都越来越大，这正是二分查找比双指针更快的原因：双指针每次最多排除一个元素，二分查找每次能排除大约一半的范围。
③ 和双指针的区别：排除速度不一样

7.1 节的对撞指针和这一节的二分查找，本质上都是利用数组的有序性，不断排除"不可能存在答案"的部分。区别在于排除的速度：对撞指针每一步只能确定排除一个元素（left 或 right 挪一格）；二分查找每一步能直接排除大约一半的剩余范围——这也是为什么二分查找的时间复杂度是 O(log n)，比双指针的 O(n) 还要快得多。

对撞指针二分查找
每一步排除的范围一个元素大约一半的剩余范围
时间复杂度O(n)O(log n)
典型场景需要同时关注两个位置的配对关系（如两数之和）只需要判断"在不在、往哪边找"
④ 完整代码与对比

数组长度 n=1000000（一百万）：

n=1,000,000 的有序数组 —— 查找一个数最坏需要多少次比较
线性查找
最多100万次
二分查找
最多20次
线性查找最坏情况要把一百万个数全部看一遍；二分查找每次排除一半，log2(1000000) ≈ 19.9，最多 20 次比较就能确定结果（或者确认不存在）——数据规模越大，二分查找的优势越是碾压性的。这也是为什么"判断能不能用二分"，往往是看到"有序"两个字之后第一个该想到的优化方向。
查找方式前提条件时间复杂度
线性查找无（数组顺序任意）O(n)
二分查找数组必须已经排好序O(log n)
🎯
二分查找的应用远不止"在数组里找一个数"——只要能把问题转化成"判断某个候选答案是否满足条件，并且满足条件的答案具有单调性（比如'够不够大''行不行得通'，越界后答案不会再变回来）"，就可以用二分去猜这个答案，这种用法叫二分答案，会在后面的进阶内容里见到。模块七到这里就结束了——双指针和二分查找，都是建立在"数据有序、可以放心排除不可能区域"这个基础上的两种不同效率的优化思路。