二分查找的失败通常不是思路错,而是边界定义含糊。写之前必须先明确一件事:区间是闭区间 [lo, hi] 还是左闭右开 [lo, hi)。
写法一:闭区间#
int lower_bound(vector<int>& a, int target) {
int lo = 0, hi = a.size() - 1; // 闭区间 [lo, hi]
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return lo; // 第一个 >= target 的位置
}
循环结束时 lo == hi + 1,并且 hi 指向最后一个小于 target 的元素,lo 指向第一个大于等于 target 的元素。这个不变式是整个写法的灵魂。
写法二:左闭右开#
int lower_bound2(vector<int>& a, int target) {
int lo = 0, hi = a.size(); // [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
这种写法里 hi 是「不可达」的边界,所以更新时是 hi = mid 而不是 mid - 1。两种写法结果一致,但循环条件从 <= 变成了 <,千万不要混用。
写法三:直接用 STL#
竞赛里更省事的是 std::lower_bound / upper_bound,但要注意它们返回的是迭代器,并且要求序列已排序。
口诀:闭区间用 <= 配 mid±1;左闭右开用 < 配 hi=mid。 只要这两个配套,就不会死循环。
最常见的一个死循环#
mid = (lo + hi) / 2 在 lo = hi - 1 时永远等于 lo,如果此时分支写成 lo = mid 就会原地打转。改成 lo = mid + 1,或者用 (lo + hi + 1) / 2 取上中位数。
小结#
写二分的正确姿势:先写清楚区间定义,再写不变式,最后才写循环体。调试时打印 lo, hi, mid 三行,绝大多数问题一眼就能看出来。