w wyl123ly 的博客
未分类 更新于 10 月 28 日

二分查找的三种写法与边界陷阱

二分查找的失败通常不是思路错,而是边界定义含糊。写之前必须先明确一件事:区间是闭区间 [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 三行,绝大多数问题一眼就能看出来。