老师给大家总结了常见二分，把各种常见二分场景拆成两大类：离散二分（在整数或下标上）和连续二分（浮点／实数），并且针对「查找第一个满足条件的位置」与「查找最后一个满足条件的位置」两种子问题，列出它们的循环条件和更新边界的套路。

一、离散二分（整数／下标）

假设我们在一个单调布尔数组或区间 \([L_0,R_0]\subseteq\mathbb Z\) 上，定义条件函数 good(mid)：若 good(mid) == true，说明“答案”在 \(\le mid\) 侧（或反过来，下面会分情况）。

情形 A：查「第一个使 good(mid)==true 的下标」

• 区间：\([L_0,R_0]\)，约定 good(x)==false 在左，true 在右，形如

  false, false, …, false  | true, true, …, true
                        ↑
                    answer
  

• 模板：

  int l = L0, r = R0;
  // 不要用 <=，否则 mid = (l+r)/2 可能陷入死循环
  while (l < r) {
      int mid = l + (r - l) / 2;
      if (good(mid)) {
          // 答案可能就是 mid，也可能在更左
          r = mid;
      } else {
          // mid 及其左边都不行，只能往右
          l = mid + 1;
      }
  }
  // 退出时 l == r，且就是第一个 good()==true 的位置
  return l;
  

• 为什么：
  • l<r 保证区间长度至少 2，每次至少缩一点；
  • r=mid 保留 mid，因为 mid 可能就是第一个 true；
  • l=mid+1 跳过所有 false，包括 mid 本身。

情形 B：查「最后一个使 good(mid)==true 的下标」

• 区间：\([L_0,R_0]\)，约定 true 在左，false 在右，形如

  true, true, …, true  | false, false, …, false
              ↑
         answer
  

• 模板：

  int l = L0, r = R0;
  while (l < r) {
      // 向上取整中点，避免 l 不动导致死循环
      int mid = l + (r - l + 1) / 2;
      if (good(mid)) {
          // mid 及其左边都是 true，答案在 [mid, r]
          l = mid;
      } else {
          // mid 一定不行，只能往左走
          r = mid - 1;
      }
  }
  // 返回 l（==r）
  return l;
  

• 关键：
  • mid = l + (r-l+1)/2 保证当 l+1==r 时，mid 总是 r，让 l=mid 能缩区间；
  • l=mid 保留 mid，因为它可能是真正的最后一个 true；
  • r=mid-1 跳过 mid 及其右侧所有 false。

小结离散二分

• 千万别用 while(l <= r) 搭配这两组写法，否则要么多一次迭代要么死循环；l<=r 更常用于「在区间内找某个固定值，返回 -1 或下标」的场景，搭配 l = mid+1/r = mid-1。

二、经典的 while (l <= r) 模板

当你想「在区间内查找整型值 x 是否存在且返回下标」，或者「枚举 mid，一旦 good(mid) 就 break」，就用这种：

int l = L0, r = R0;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (A[mid] == target) {
        return mid;
    } else if (A[mid] < target) {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}
// 没找到
return -1;

• l<=r 保证所有下标都被试到；
• l=mid+1 和 r=mid-1 保证区间在每次迭代都严格收缩。

三、连续二分（浮点／实数）

常用于「在实数区间上找一个满足单调条件的边界」，比如最小化／最大化函数值等。一般写：

double l = L0, r = R0;
for (int it = 0; it < ITER; it++) {
    double mid = (l + r) / 2;
    if (good(mid)) {
        r = mid;    // 或者 l = mid，视具体找左边界还是右边界
    } else {
        l = mid;
    }
}
double ans = (l + r) / 2;

• 取 ITER 足够大（如 60 次）或用 while (r-l > eps)。
• 更新时用 l=mid、r=mid（不加减 1，因为这里不是离散的，mid±eps 本质上也是这样做）。

四、如何快速选用套路

1. 找下标／整数的第⼀个/最后⼀个 ⇒ 用「while(l<r) , 分两种 mid 取法」的 情形A/B。
2. 判断某值是否存在并返回下标 ⇒ 用「while(l<=r) , l=mid+1/r=mid-1」。
3. 找实数最优点 ⇒ 用「while(r-l>eps) 或固定迭代次数 , l=mid/r=mid」。

掌握这三类，就能应对市面上几乎所有二分问题。只要记住：

• l<r 用于「缩区间到只剩一个答案」；
• l<=r 用于「在区间里找某个值／突破平局」；
• mid 向下／向上取整 决定保留哪端。

祝你边界无忧，二分必胜！