C++ 算法技巧 — 二分查找 (Binary Search)

章节概述

二分查找在有序序列中每次将查找范围减半，将查找复杂度从 O(n) 降至 O(log n)。
是算法竞赛中最基础也最重要的优化手段之一。

核心原理

1. 数学基础

在有序数组 a[1..n] 中查找目标值 x，每次取中点 mid = (l+r)/2：

若 a[mid] == x：找到目标
若 a[mid] < x：目标在右半，l = mid + 1
若 a[mid] > x：目标在左半，r = mid - 1

每步将搜索空间减半，时间复杂度：
$T (n) = T (n /2) + O (1) = O (lo g n)$

对 100 万元素，最多比较约 20 次。

2. 两种终止条件

写法	条件	结束状态	适用场景
`while(l <= r)`	l > r 时退出	l = r+1	精确查找
`while(l < r)`	l == r 时退出	l = r	查找边界（lower_bound）

3. 三个核心变体

变体	含义	实现
`lower_bound`	第一个 ≥ x 的位置	`a[mid] >= x` 时 `r = mid - 1`
`upper_bound`	第一个 > x 的位置	`a[mid] > x` 时 `r = mid - 1`
`binary_search`	是否存在 x	标准二分查找到即返回

4. 防溢出技巧

int mid = l + (r - l) / 2; // 安全，不会溢出
// 而非 mid = (l + r) / 2; // l+r 可能溢出

关键数据结构

E_容器_Container — vector 的随机访问使二分查找 O(log n)
I_排序_八大排序_Sorting — 排序是二分查找的前提

P2249 查找

题目: 输入 n 个单调不减的非负整数，然后 q 次询问，每次询问数字 x 第一次出现的位置（从 1 开始编号）。若不存在则输出 -1。

思路: 使用 lower_bound 二分查找第一个 ≥ x 的位置，再判断是否等于 x。

#include <iostream>
using namespace std;
int a[1000005];
 
int main() {
 int n, q;
 cin >> n >> q;
 for (int i = 1; i <= n; i++) cin >> a[i];
 while (q--) {
 int x;
 cin >> x;
 int l = 1, r = n, ans = -1;
 while (l <= r) {
 int mid = (l + r) / 2;
 if (a[mid] >= x) {
 ans = mid;
 r = mid - 1;
 } else {
 l = mid + 1;
 }
 }
 if (ans != -1 && a[ans] == x)
 cout << ans << " ";
 else
 cout << -1 << " ";
 }
 return 0;
}

P1102 A-B 数对

题目: 给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A-B=C 的数对 (A,B) 的个数。
不同位置的数字一样属于不同的数对。

思路: 对于每个 A，求 B=A-C 在数组中的出现次数。用二分查找找到 B 的左右边界。

#include <iostream>
#include <algorithm>
using namespace std;
int a[200005];
 
int main() {
 int n, c;
 long long ans = 0;
 cin >> n >> c;
 for (int i = 0; i < n; i++) cin >> a[i];
 sort(a, a + n);
 for (int i = 0; i < n; i++) {
 int target = a[i] - c;
 int l = lower_bound(a, a + n, target) - a;
 int r = upper_bound(a, a + n, target) - a;
 ans += r - l;
 }
 cout << ans << endl;
 return 0;
}

P1678 烦恼的高考志愿

题目: 有 m 所学校每所预计分数线为 b_j，有 n 个学生每个考分为 a_i。每个学生的”不满意度”为其分数与
所选学校分数线的差的绝对值的最小值。求所有学生不满意度之和的最小值。

思路: 将学校分数线排序，对每个学生二分查找最接近的分数线，计算差值。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int b[100005];
 
int main() {
 int m, n;
 long long ans = 0;
 cin >> m >> n;
 for (int i = 0; i < m; i++) cin >> b[i];
 sort(b, b + m);
 for (int i = 0, x; i < n; i++) {
 cin >> x;
 int pos = lower_bound(b, b + m, x) - b;
 int diff = 2e9;
 if (pos < m) diff = min(diff, abs(b[pos] - x));
 if (pos > 0) diff = min(diff, abs(b[pos - 1] - x));
 ans += diff;
 }
 cout << ans << endl;
 return 0;
}

RootStack

探索

C++ 算法技巧 — 二分查找 (Binary Search)

章节概述

核心原理

关键数据结构

P2249 查找

P1102 A-B 数对

P1678 烦恼的高考志愿

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接