二分法不只是"在有序数组中查找"，它的应用远比想象中广泛。
一、二分查找基础
- 在有序数组中查找特定值
- lower_bound：第一个 >= x 的位置
- upper_bound：第一个 > x 的位置
- 编程技巧：左闭右开区间 [l, r)
二、二分答案（核心思想）
当问题满足单调性时，可以把优化问题转化为判定问题。
经典套路：
- 发现答案具有单调性（如果 x 可行，则 > x 也可行 / < x 也可行）
- 二分答案值 mid
- 设计 check(mid) 判断是否可行
- 根据 check 结果收缩区间
典型例题：
- 洛谷 P2678 跳石头（最小距离最大化）
- 洛谷 P1314 聪明的质监员
- 洛谷 P1083 借教室
三、二分套二分
外层二分答案，内层再用二分求解子问题，常见于带多维约束的优化问题。
四、三分搜索
用于求单峰/单谷函数的极值。
while (r - l > eps) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(m1) < f(m2)) l = m1;
else r = m2;
}五、WQS 二分（带权二分 / 凸优化）
解决"恰好选 K 个"的优化问题，通过给每个选择附加一个代价来消除数量限制。
六、整体二分
同时处理多个询问，对所有询问一起二分答案，常用于静态区间第 k 小等问题。
二分答案 checklist：
- 候选答案是否连续？
- 判定函数 check 是否高效（通常 O(n) 或 O(n log n)）？
- 边界条件是否处理正确？
暂无评论，快来抢沙发吧~ 🛋️