二分查找的四种写法（关键行注释版）

二分查找（Binary Search）是信奥与算法竞赛的基石。同一个「在有序里找东西」的需求，根据区间定义、循环条件、目标的不同，有四种最常见、也最容易写错的写法。下面每种都在关键代码行的上方独立注释，方便逐行理解。

写法一：左闭右闭 [l, r] —— 找精确值（最直观）

int binary_search(int a[], int n, int key) {
    // 区间 [l, r] 闭区间，初始覆盖全部元素
    int l = 0, r = n - 1;
    // 区间非空才继续；l==r 时还剩 1 个元素要判
    while (l <= r) {
        // 防溢出写法，等价于 (l+r)/2
        int mid = l + (r - l) / 2;
        // 命中，直接返回下标
        if (a[mid] == key) return mid;
        // key 在右半，左边界右移（mid 已排除）
        else if (a[mid] < key) l = mid + 1;
        // key 在左半，右边界左移（mid 已排除）
        else r = mid - 1;
    }
    // 区间为空仍未命中
    return -1;
}

写法二：左闭右开 [l, r) —— 找下界（lower_bound）

int lower_bound(int a[], int n, int key) {
    // 区间 [l, r)，右端点取 n（开区间，r 不可取）
    int l = 0, r = n;
    // 区间非空条件变成 l < r（l==r 时区间已空）
    while (l < r) {
        int mid = l + (r - l) / 2;
        // mid 满足“≥key”→ 答案在 [l, mid]（保留 mid）
        if (a[mid] >= key) r = mid;
        // mid 不满足 → 答案在 (mid, r)
        else l = mid + 1;
    }
    // 退出时 l==r，即第一个 ≥ key 的位置
    return l;
}

把 a[mid] >= key 改成 a[mid] > key，就是 upper_bound（第一个 > key 的位置）。

写法三：通用边界模板（yxc 风格）—— 二分答案的基石

// 找【最小】的使 check 为真的位置（左边界）
int find_first_true(int l, int r) {
    // 答案保证在 [l, r] 内
    while (l < r) {
        // 中点偏左（向下取整）
        int mid = l + (r - l) / 2;
        // mid 满足 → 答案在 [l, mid]（保留 mid）
        if (check(mid)) r = mid;
        // mid 不满足 → 答案在 (mid, r]
        else l = mid + 1;
    }
    // 退出时 l==r
    return l;
}

// 找【最大】的使 check 为真的位置（右边界）
int find_last_true(int l, int r) {
    while (l < r) {
        // ★ 中点偏右（向上取整），错写会死循环
        int mid = l + (r - l + 1) / 2;
        // mid 满足 → 答案在 [mid, r]（保留 mid）
        if (check(mid)) l = mid;
        // mid 不满足 → 答案在 [l, mid)
        else r = mid - 1;
    }
    return l;
}

把 check(mid) 理解为「以 mid 作为答案是否可行」，这套模板就是二分答案本体。

写法四：浮点二分 —— 求满足精度的值

double fbinary_search(double l, double r, double eps) {
    // ★ 用精度控制循环，绝不能写 l < r（会死循环）
    while (r - l > eps) {
        // 浮点直接取中点，无需防溢出偏左
        double mid = (l + r) / 2;
        // 满足 → 答案在左半 [l, mid]
        if (check(mid)) r = mid;
        // 不满足 → 答案在右半 [mid, r]
        else l = mid;
    }
    // 精度足够，返回 l 或 mid 都行
    return l;
}

速查表

五个坑

1. 写法三右边界漏写 mid = (l+r+1)/2 → 死循环。
2. (l+r) 大数溢出 → 一律用 l + (r-l)/2。
3. 闭区间配 l<=r、开区间配 l<r，混用必错。
4. 浮点写 l<r → 死循环，要用精度 eps（比题目要求精度再小约 2 个数量级）。
5. 二分答案把 check 方向写反 → 答案全反，模板只是壳，check 才是灵魂。

本站原创整理，代码以 C++ 为准；OJ 提交前请按题目调好数据类型与精度。转载请注明出处。