跳转至

二分与三分查找

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

整数二分模版

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

模式一：寻找满足条件的第一个位置（左边界 / 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 经典真题精选与题解提示

  • LeetCode 33 - 搜索旋转排序数组 (Search in Rotated Sorted Array) 中等

    提示

    局部单调性二分决策。

    • 取中点 \(mid\) 后，整个区间被切分成两半，其中必定有一半是完全单调有序的。
    • 通过比较 \(nums[l]\) 与 \(nums[mid]\) 可确定左半部分是否严格有序。在确定有序的一半区间内根据 \(target\) 的范围直接判断下一步缩减方向。

  • LeetCode 34 - 在排序数组中查找元素的第一个和最后一个位置 (Find First and Last Position of Element in Sorted Array) 中等

    提示

    红蓝开闭区间标杆。

    • 分别调用两次二分查找：首个 \(\ge target\) 的下标（lower_bound），以及首个 \(> target\) 的下标（upper_bound）减 1。
    • 检查越界与元素相等性即可确定区间 \([first, last]\)。

  • LeetCode 153 - 寻找旋转排序数组中的最小值 (Find Minimum in Rotated Sorted Array) 中等

    提示

    比较基准点收缩。

    • 始终以右端点 \(nums[r]\) 作为比较参考系：若 \(nums[mid] < nums[r]\)，说明最小值必定落在左半段（含 \(mid\)），令 \(r = mid\)；
    • 若 \(nums[mid] > nums[r]\)，说明最小值必定落在右半段，令 \(l = mid + 1\)。

  • LeetCode 162 - 寻找峰值 (Find Peak Element) 中等

    提示

    局部二分爬坡模型。

    • 比较 \(nums[mid]\) 与 \(nums[mid + 1]\)：若处于上升坡（\(nums[mid] < nums[mid + 1]\)），则右侧必定存在至少一个峰值，令 \(l = mid + 1\)；
    • 若处于下降坡，则左侧（含 \(mid\)）必定存在峰值，令 \(r = mid\)。严格 \(\mathcal{O}(\log N)\)。

  • LeetCode 410 - 分割数组的最大值 (Split Array Largest Sum) 困难

    提示

    二分答案判定模型标杆。

    • 判定函数具备单调性：若子数组各自和的最大值上限为 \(M\)，贪心累加当前段，超过 \(M\) 则开启新段，统计所需段数是否 \(\le k\)。
    • 二分范围：下界为 \(\max(nums)\)，上界为 \(\sum nums\)。

  • LeetCode 875 - 爱吃香蕉的柯珂 (Koko Eating Bananas) 中等

    提示

    最值速度二分答案。

    • 速度 \(v\) 越快，吃完所需时间总和单调递减。
    • 二分吃香蕉速度 \(v \in [1, \max(piles)]\)，单次检验计算 \(\sum \lceil pile / v \rceil \le h\)。

  • LeetCode 719 - 找出第 K 小的数对距离 (Find K-th Smallest Pair Distance) 困难

    提示

    值域二分答案 + 双指针滑动窗口计数。

    • 将数组排序。数对距离的值域区间为 \([0, nums[n-1] - nums[0]]\)；
    • 二分目标距离 \(mid\)，判断距离 \(\le mid\) 的数对总数是否 \(\ge k\)；
    • 计数利用有序双指针：右指针 \(r\) 推进，左指针 \(l\) 追赶，满足 \(nums[r] - nums[l] \le mid\)，当前以 \(r\) 为右端点的合法数对数为 \(r - l\)，单次检验 \(\mathcal{O}(N)\)，总复杂度 \(\mathcal{O}(N \log N + N \log(\max - \min))\)。

  • LeetCode 2040 - 两个有序数组的第 K 小乘积 (Kth Smallest Product of Two Sorted Arrays) 困难

    提示

    乘积值域二分答案 + 正负分类双指针。

    • 乘积值域范围跨越 \([-10^{10}, 10^{10}]\)；
    • 二分猜测乘积上限 \(mid\)，统计两个数组中满足 \(nums1[i] \times nums2[j] \le mid\) 的数对数量；
    • 按 \(nums1[i]\) 的正负零符号严格分类讨论：正数时 \(nums2\) 单调正序双指针，负数时不等号变向逆向双指针，零时直接根据 \(mid \ge 0\) 判断。