C++ · 算法策略
二分查找
用区间减半过程解释二分查找的 O(log n)，通过 C++ lower_bound 与重复值计数例子检查半开区间和结束位置。
有序区间、单调条件与二分边界
对非降序数组，条件 a[i]≥x 呈现“前假后真”，可以寻找真假分界。
使用半开区间 [l,r)，初始 l=0、r=n。取 mid=l+(r−l)/2；若 a[mid]≥x，则令 r=mid，否则令 l=mid+1。结束时 l=r，是第一个不小于 x 的位置，可能等于 n。
每轮区间都缩小，查询时间 O(log n)。查找“是否存在”时，还要确认位置小于 n 且对应值等于 x。upper_bound 则寻找第一个严格大于 x 的位置，两者相减得到等于 x 的元素数量。
为什么二分查找是 O(log n)
把候选区间长度想成 16→8→4→2→1：每次判断都排除约一半。经过 k 次减半，剩余规模约为 n/2ᵏ；令其接近 1，得到 k≈log₂n。具体循环次数受中点与边界写法影响，不应把 log₂n 当作所有输入的精确次数。
本页在数组上实现 lower_bound，使用 [l, r) 查找第一个不小于目标的位置；遇到相等值也继续向左收缩。与“中点相等就返回”的普通查找不同，这份边界查找不能靠第一次相等直接结束。若没有合适元素，返回 n，访问 a[n] 前必须检查。一般查找的最好情况可为 O(1)，最坏 O(log n)；这里非空数组上的这份 lower_bound 实现要持续缩小到边界，比较次数为 Θ(log(n+1))，辅助空间 O(1)。
先自己判断：在 [1, 2, 2, 4] 中查找第一个不小于 2 的下标，应返回哪个位置？
返回 1，不是 2。即使中点等于 2，也要继续检查左侧边界。
lower_bound 与重复值计数
例1：手写 lower_bound
#include <iostream>
#include <vector>
using namespace std;
int lower(const vector<int>& a, int x) {
int l = 0, r = a.size();
while (l < r) {
int m = l + (r - l) / 2;
if (a[m] >= x) r = m; else l = m + 1;
}
return l;
}
int main() {
vector<int> a = {1, 3, 3, 8};
cout << lower(a, 3) << " " << lower(a, 9) << endl;
}输出 1 4。3 的第一次出现位于下标 1，9 的插入位置为末尾 4，不能访问 a[4]。
例2：两个边界统计重复值
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> a = {1, 3, 3, 3, 8};
cout << upper_bound(a.begin(), a.end(), 3) - lower_bound(a.begin(), a.end(), 3) << endl;
}输出 3。第一个大于 3 的位置减第一个不小于 3 的位置，正好是重复段长度。
提示
- 二分的前提是有序或条件单调，不能直接对乱序数组使用。
- 找到候选位置不等于找到了目标，必须再判断边界和相等。
- 不要混用闭区间的 r=mid−1 与本例半开区间的 r=mid。
先修知识
技术参考
范围说明
本站讲解由 InfoCode 编写，不是官方考纲；参考级别是本站映射，不代表官方等级、认证或参赛资格。练习记录不等于掌握或资格。
参考级别：GESP 5 级（本站映射）