跳转至

二分与三分查找

二分查找是算法竞赛中最为基础且核心的优化技巧，广泛应用于单调性判定问题（二分答案）与区间定位。三分法则常用于单峰/单谷函数的极值求解。

整数二分模版

整数二分的关键在于区间定义以及更新方式。推荐掌握以下两种开/闭区间常用模式，彻底杜绝死循环。

模式一：寻找满足条件的第一个位置（左边界 / lower_bound 语义）

在区间 \([L, R]\) 内找到满足 check(mid) == true 的最小索引：

int l = 0, r = n - 1;
int ans = -1; // 默认无解

while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;     // 记录当前可行解
        r = mid - 1;   // 尝试寻找更小的可行解
    } else {
        l = mid + 1;
    }
}

模式二：寻找满足条件的最右位置（右边界 / upper_bound 语义）

在区间 \([L, R]\) 内找到满足 check(mid) == true 的最大索引：

int l = 0, r = n - 1;
int ans = -1;

while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;     // 记录当前可行解
        l = mid + 1;   // 尝试寻找更大的可行解
    } else {
        r = mid - 1;
    }
}

小技巧：使用 l + (r - l) / 2 代替 (l + r) / 2 可以避免由于 l + r 超过整型最大值而导致的整型溢出。

浮点数二分模版

浮点数二分无需考虑整型除法向下取整造成的边界问题，通常有两种控制终止的方式：固定精度 \(\text{eps}\) 或固定循环次数。

推荐在实数二分中直接固定迭代循环 80~100 次。不仅编码极简，且精度可达到 \(2^{-100} \approx 10^{-30}\)，彻底避免由于浮点精度抖动导致的死循环。

double l = 0.0, r = 1e9;
for (int iter = 0; iter < 100; ++iter) {
    double mid = (l + r) / 2.0;
    if (check(mid)) {
        r = mid;
    } else {
        l = mid;
    }
}
// 最终解为 l (或 r)

const double eps = 1e-8;
double l = 0.0, r = 1e9;
while (r - l > eps) {
    double mid = (l + r) / 2.0;
    if (check(mid)) {
        r = mid;
    } else {
        l = mid;
    }
}

三分查找适用于在连续区间内寻找严格凸函数（或凹函数/单峰函数）的极值点。

实数域三分

设函数 \(f(x)\) 在 \([l, r]\) 上先严格递增后严格递减（求最大值）：

double l = -1e9, r = 1e9;
for (int iter = 0; iter < 100; ++iter) {
    double m1 = l + (r - l) / 3.0;
    double m2 = r - (r - l) / 3.0;
    if (f(m1) < f(m2)) {
        l = m1; // 极大值位于 [m1, r]
    } else {
        r = m2; // 极大值位于 [l, m2]
    }
}
// 最终极值点约为 l

整数域三分

在离散整数区间内三分时，当区间长度较小时直接暴力枚举所有点取最值最稳妥。

ll l = 0, r = 1e12;
while (r - l > 3) {
    ll m1 = l + (r - l) / 3;
    ll m2 = r - (r - l) / 3;
    if (f(m1) < f(m2)) {
        l = m1;
    } else {
        r = m2;
    }
}
// 在剩余小区间 [l, r] 内暴力找出极值
ll ans_val = f(l);
ll best_x = l;
for (ll i = l + 1; i <= r; ++i) {
    ll cur = f(i);
    if (cur > ans_val) {
        ans_val = cur;
        best_x = i;
    }
}

3. LeetCode 经典真题精选与题解提示