二分算法

核心思想：边界理论

在实际题目中，我们往往是在一个排好序或具有单调性的序列中，寻找某种性质的分界点。
想象整条轴被某种性质分成了两部分：左边不满足条件（蓝色），右边满足条件（红色）。二分的目的就是找到红色的起点（左边界）或蓝色的终点（右边界）。

整数二分

为了彻底避免死循环，根据 mid 的归属和区间的收缩方向，将模板分为以下两种。

1. 寻找左边界 —— Lower Bound（满足条件的最小值）

• 适用场景：求满足 check 条件的最小值。
• 区间状态：当 mid 满足条件时，解在左边（包含 mid），所以 r = mid；不满足时，解在右边（不包含 mid），所以 l = mid + 1。

int find_left_boundary(int l, int r) {
 while (l < r) {
 int mid = l + (r - l) / 2; // 向下取整
 if (check(mid)) {
 r = mid; // mid满足条件，说明答案在左边（包含mid）
 } else {
 l = mid + 1; // mid不满足条件，答案在mid右边
 }
 }
 return l; // 此时 l == r
}

2. 寻找右边界 —— Upper Bound（满足条件的最大值）

• 适用场景：求满足 check 条件的最大值。
• 区间状态：当 mid 满足条件时，解在右边（包含 mid），所以 l = mid；不满足时，解在左边（不包含 mid），所以 r = mid - 1。

int find_right_boundary(int l, int r) {
 while (l < r) {
 int mid = l + (r - l + 1) / 2;//✨ 向上取整，整体右偏，防止死循环
 if (check(mid)) {
 l = mid;//mid满足条件，说明答案在右边（包含mid）
 } else {
 r = mid - 1;//mid不满足条件，答案在mid左边
 }
 }
 return l; // 此时l == r
}

⚠️ 死循环防错核心：在模板 2 中，若区间缩水到 l = 0, r = 1 且 check(0) 为真。如果使用向下取整，mid 会一直为 0，执行 l = mid 后区间没有任何变化，从而陷入死循环。加上 + 1 变为向上取整后，mid 为 1，无论是执行 l = 1 还是 r = 0，区间都会收缩，完美避开死循环。

特判

// 以寻找左边界（第一个 >= X 的数）为例，数组大小为 N
int ans_idx = find_left_boundary(0, N);//[0,N)

if (ans_idx == N) {
 // 情况 A：所有数都比 X 小，指针越过数组末尾
 printf("不存在满足条件的数（全部偏小）\n");
} else if (a[ans_idx] != X) { 
 // 情况 B：指针合法，但值不等于 X（说明找到了第一个大于 X 的数）
 printf("没有精确相等的数，第一个大于 X 的数下标为: %d\n", ans_idx);
} else {
 // 情况 C：找到了精确相等的数
 printf("成功找到目标，下标为: %d\n", ans_idx);
}

实数二分

实数二分由于没有离散整除的困扰，不需要考虑 +1 或 -1。但使用 while (r - l > eps) 容易因精度误差（如 eps 设得过小）导致死循环 TLE。

✨ 终极推荐：固定次数循环法

// 循环 100 次，区间减半至 2^{-100}，远超 double 的精度极限
for (int i = 0; i < 100; i++) {
 double mid = l + (r - l) / 2.0;
 if (check(mid)) r = mid; 
 else l = mid;
}
// 此时 l 和 r 极度逼近，直接返回 l 即可

• 优势：绝对不会死循环；精度达到计算机表示极限；运行时间极其稳定，不受数据范围影响。