二分算法详解：从整数二分到浮点二分，彻底搞懂边界问题

前言

二分法（Binary Search）是算法竞赛中最基础、最常用的算法之一。它通过每次将搜索区间一分为二，以 O(log n) 的时间复杂度快速找到目标值或满足条件的边界。然而，二分的边界处理、循环条件、返回值等问题常常让初学者感到困惑。本文将从我个人常用的 “红绿模型” 出发，系统讲解整数二分的两种经典写法，最后也会给出浮点二分写法。

---

本讲法参考该视频，读者可前往学习二分查找为什么总是写错

一、二分法的核心思想

二分法必须在 具有单调性的区间 上使用。例如一个升序数组 [1, 3, 5, 7, 9]，我们要查找 第一个 ≥5 的元素位置（下标从 1 开始），答案是 3。

二分法的基本步骤：

1. 确定搜索区间 [L+1, R-1]，或[L, R]。
2. 取中点 mid = (L + R) / 2（注意整数除法向下取整）。
3. 根据 mid 处元素是否满足某种性质，决定舍弃左半部分或右半部分。
4. 重复直到区间缩小到答案位置。

不同的问题可能要求查找：

• 第一个 ≥ x 的位置
• 第一个 > x 的位置
• 最后一个 < x 的位置
• 最后一个 ≤ x 的位置

针对这些不同需求，二分写法需要微调。下面介绍两种我个人认为最容易理解的写法。

---

二、整数二分：红绿模型（开区间写法）

2.1 模型解释

将整个区间划分为 红色区间 和 绿色区间，分别代表 不满足条件 和 满足条件 的部分。定义：

• L：红色区间的右端点（最后一个红色的位置）
• R：绿色区间的左端点（第一个绿色的位置）

初始化时，L 和 R 位于实际区间 边界之外（例如数组下标从 1 到 n，则 L=0, R=n+1），因为最初我们不知道任何元素属于红还是绿。

循环条件：R - L > 1（红绿区间未相邻时继续）
更新规则：

• 若 mid 满足绿色性质 → R = mid（绿色区间向左扩展）
• 否则（红色性质）→ L = mid（红色区间向右扩展）

循环结束后，R 就是第一个满足绿色性质的位置，L 是最后一个不满足性质的位置。根据具体问题返回 R 或 L。

2.2 示例演示

在数组 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 中查找 第一个 ≥13 的位置（下标从 1 开始）。
轮次1：


轮次2：


轮次3：

轮次4：


最终结果：

轮次	L	R	mid	a[mid]	a[mid] ≥ 13?	操作
1	0	11	5	9	否（红）	L = 5
2	5	11	8	15	是（绿）	R = 8
3	5	8	6	11	否（红）	L = 6
4	6	8	7	13	是（绿）	R = 7

此时 R - L = 1，循环结束，返回 R = 7，即第一个 ≥13 的位置。

注意：即使 mid 恰好等于目标值，依然按绿色区间处理，继续向左压缩，最终 R 会停在第一个绿色位置。

2.3 代码模板（红绿模型）

// 查找第一个满足 isGreen 条件的位置（返回下标）
int find(int a[], int n, int x) {
    int l = 0, r = n + 1;          // 区间为 (l, r)，开区间
    while (r - l > 1) {
        int mid = (l + r) / 2;     // 向下取整
        if (isGreen(a[mid], x))    // 满足绿色条件,则将r扩展至mid
            r = mid;
        else
            l = mid;
    }
    return r;                      // r 是第一个绿色位置
}

// 判断绿色条件（示例：查找第一个 >= x）
bool isGreen(int val, int x) {
    return val >= x;
}

优点：逻辑清晰，边界无需额外处理，不会死循环。
适用场景：查找满足/不满足某种性质的分界点（如第一个 ≥ x、第一个 > x、最后一个 < x 等）。

---

三、整数二分：闭区间写法（常见写法）

闭区间写法直接操作 [L, R]，循环条件为 L <= R，更新时通过 mid ± 1 来缩小区间。

3.1 代码模板

// 查找第一个 >= x 的位置
int binarySearch(int a[], int n, int x) {
    int l = 1, r = n;          // 闭区间 [l, r]
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] >= x)
            r = mid - 1;       // 满足条件，向左收缩
        else
            l = mid + 1;       // 不满足，向右收缩
    }
    return l;                  // 循环结束后 l 就是第一个满足条件的位置
}

解释：

• 当 a[mid] >= x 时，说明答案在 [l, mid] 中，但 mid 可能不是第一个，因此令 r = mid - 1。
• 当 a[mid] < x 时，说明答案在 [mid+1, r] 中，令 l = mid + 1。
• 循环结束时 l = r + 1，l 指向第一个满足条件的位置，r 指向最后一个不满足的位置。

3.2 不同查找目标的修改

目标	判断条件 (a[mid] ... x)	满足时操作	不满足时操作	最终返回
第一个 ≥ x	>= x	r = mid-1	l = mid+1	l
第一个 > x	> x	r = mid-1	l = mid+1	l
最后一个 < x	< x	l = mid+1	r = mid-1	r
最后一个 ≤ x	<= x	l = mid+1	r = mid-1	r

记忆技巧：l 最终指向 第一个满足条件 的位置，r 指向 最后一个不满足条件 的位置。

---

四、浮点数二分

浮点数二分过于简单，无需考虑边界问题，故不做过多讲解
当我们需要在实数范围内求某个方程的根、或求满足精度的最值时，使用浮点数二分。与整数二分的区别在于：

• 无需处理边界 ±1，直接 mid = (l + r) / 2
• 循环条件通常用 r - l > eps，其中 eps 为允许的误差（如 1e-6 或 1e-8）

4.1 代码模板（求平方根）

double sqrt_binary(double x) {
    double l = 0, r = x;
    if (x < 1) r = 1;          // 处理 x 在 (0,1) 的情况
    double eps = 1e-8;         // 精度控制
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (mid * mid >= x)
            r = mid;           // 满足条件，向左逼近
        else
            l = mid;
    }
    return l;                  // 或返回 (l+r)/2
}

4.2 注意事项

• 精度选择：一般比题目要求多 2~3 位小数。若要求保留小数点后 6 位，则 eps = 1e-8。
• 循环条件：r - l > eps 也可改为 for (int i = 0; i < 100; ++i) 固定迭代次数（更安全，不依赖精度）。
• 初始区间：根据函数单调性合理设定，避免根在区间外。

4.3 应用举例：求三次方程的根

对于单调函数 f(x) = x^3 - x - 1 在区间 [1,2] 内的零点：

double f(double x) { return x*x*x - x - 1; }
double findRoot() {
    double l = 1, r = 2, eps = 1e-8;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (f(mid) >= 0) r = mid;
        else l = mid;
    }
    return (l + r) / 2;
}

---

五、总结与易错点提醒

易错点	解决方案
整数二分死循环	使用红绿模型（r-l>1）或闭区间正确更新 ±1
初始边界错误	红绿模型初始 L=0, R=n+1；闭区间初始 L=1, R=n（下标从1起）
浮点数精度不够	取 eps = 1e-8 或固定循环100次
返回 L 还是 R 混淆	牢记：红绿模型中 R 是第一个绿色；闭区间中 L 是第一个满足条件的位置

二分算法看似简单，但细节决定成败。希望本文的“红绿模型”和闭区间对比能帮助你彻底告别边界恐惧。在解决实际问题时，可以先判断单调性，再选择合适的模板，最后针对目标调整判断条件和返回值。

---

初次撰写，有不足的地方望大家提出，督促作者更改
2026-4-4