illegalCreed

中文

English

中文

English

Appearance

边界与坑：死循环、溢出与退出条件 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 死循环的头号元凶：l = mid（向下取整时）——当 l + 1 === r 且 mid = l + ((r-l)>>1) === l 时，a[mid] 满足保留条件让 l = mid，l 没动，区间不缩，永远跳不出。修法：求右边界时 mid 向上取整 l + ((r-l+1)>>1)。
  • mid 整型溢出：(l + r) / 2 在 l + r 超过整型上限（如 32 位 INT_MAX）时溢出成负数，下标越界。修法：mid = l + ((r - l) >> 1)（减法不溢出）。
  • 退出条件混淆 while (l <= r) vs while (l < r)：取决于区间开闭——闭区间 [l,r] 用 l <= r（l===r 仍是单元素区间）；半开 [l,r) 用 l < r（l===r 区间空）。混用要么漏查元素、要么死循环。
  • 返回值含义混淆：精确查找返回「命中下标或 -1」；左边界返回「第一个 >= target 的位置」（可能越界到 n）；右边界返回「最后一个 <= target 的位置」——三者语义不同，别套混。
  • 收缩时该排除却保留（或反之）：mid 已确认非答案却不 ±1 排除 → 死循环；mid 可能是答案却 ±1 排除 → 漏解。判断标准：「mid 是否可能是答案」。
  • 忘记 mid 已与 target 比较过：精确查找里 a[mid] 比 target 后已确认不是答案，必须从区间彻底排除；左/右边界里 a[mid] 可能是答案才保留——两者别搞反。
  • 判断「target 是否存在」要额外检查：左边界返回的位置 l 不一定是 target 本身（可能 a[l] > target），需 l < n && a[l] === target 才算存在。
  • 空数组 / 单元素数组边界：n === 0 时 r = -1（闭区间），while (l <= r) 直接不进，返回 -1 正确；但要确认初始值没写错。
  • 统一心法：先定区间开闭 → 再定退出条件 → 最后定收缩方式，三者自洽即对；任何一环不自洽就出错。
  • 验证技巧：写完二分，用 n=1、n=2、target 在首/末/不存在四个 case 手推一遍，能抓住绝大多数边界 bug。

一、死循环：l = mid 配向下取整的陷阱 ​

死循环是二分最隐蔽的 bug——程序不报错，只是「卡住」。头号元凶是**「求右边界时 mid 向下取整 + l = mid」**。

js
// ❌ 错误写法：求最后一个 <= target，会死循环
function badUpperBound(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const mid = l + ((r - l) >> 1);     // 向下取整
    nums[mid] <= target ? (l = mid) : (r = mid - 1); // l = mid！
  }
  return l;
}

死循环过程：当 l + 1 === r（区间只剩两个候选）时，mid = l + ((r-l) >> 1) = l + 0 = l（向下取整）。若 a[mid] <= target，执行 l = mid = l——l 没变，l < r 仍成立，下一轮 mid 还是 l，永远跳不出。

修法：求右边界（l = mid 的场景）时，mid 改用向上取整：

js
// ✅ 正确写法：mid 向上取整
function goodUpperBound(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const mid = l + ((r - l + 1) >> 1); // 向上取整！
    nums[mid] <= target ? (l = mid) : (r = mid - 1);
  }
  return l;
}

向上取整后，l + 1 === r 时 mid = l + 1 = r，l = mid = r 让 l 前进到 r，l < r 变 false，循环结束。

记忆口诀：「l = mid 配向上取整，r = mid 配向下取整」。因为 l = mid 要让 mid 偏右才能前进，r = mid 要让 mid 偏左才能后退。

二、mid 整型溢出：l + r 的陷阱 ​

(l + r) / 2 在 l 和 r 都很大时会溢出：

js
// ❌ 溢出写法（l + r 超过 Number.MAX_SAFE_INTEGER 或 32 位 INT_MAX）
const mid = (l + r) / 2;

// ✅ 防溢出写法（r - l 不溢出）
const mid = l + ((r - l) >> 1);   // 向下取整
const mid = l + ((r - l + 1) >> 1); // 向上取整（求右边界）
  • 32 位整型场景（C/C++/Java 的 int）：l + r 超过 2^31 - 1 时溢出成负数，a[负数] 越界段错误。这是经典面试题「LeetCode 278 第一版错误的版本」的考点。
  • JS 场景：JS 的 Number 是双精度浮点，整数安全范围到 2^53 - 1，一般不会溢出，但位运算 >> 会先转 32 位整型——若 l + r 超过 2^31，(l + r) >> 1 仍会出错。所以即便 JS 也应养成写 l + ((r - l) >> 1) 的习惯。
  • 为什么 r - l 不溢出：l、r 都是合法下标（0 <= l <= r < n），r - l 必在 [0, n) 内，远小于整型上限。

一句话：永远写 l + ((r - l) >> 1)，不写 (l + r) / 2——这是肌肉记忆，零成本防溢出。

三、退出条件：while (l <= r) vs while (l < r) ​

退出条件由区间开闭决定，混用是漏解或死循环的高频原因。

js
// 左闭右闭 [l, r]：while (l <= r)
let l = 0, r = n - 1;
while (l <= r) { /* l === r 时仍是单元素区间，要查 */ }

// 左闭右开 [l, r)：while (l < r)
let l = 0, r = n;
while (l < r) { /* l === r 时区间空，退出 */ }

// 左开右开 (l, r)：while (l + 1 < r)
let l = -1, r = n;
while (l + 1 < r) { /* l+1 === r 时区间空，退出 */ }
  • 闭区间用 l <= r：l === r 时区间里还有一个元素 a[l] 没查，必须继续；只有 l > r 才算「区间空」。若误用 l < r，会漏查最后一个元素。
  • 半开区间用 l < r：l === r 时左闭右开区间 [l, l) 是空的（左闭到右开但相等），应退出。若误用 l <= r，l === r 时进循环，mid = l，可能死循环或访问越界。

记忆口诀：「退出条件 = 区间非空的判据」——闭区间非空要 l <= r，半开非空要 l < r。

四、返回值含义：精确 / 左边界 / 右边界不同 ​

三种查找目标的返回值语义完全不同，套混是另一个高频 bug：

查找目标返回值target 不存在时典型应用
精确命中命中下标-1判断元素是否在
左边界第一个 >= target 的下标「应插入位置」（可能 = n）插入点、求首次出现
右边界最后一个 <= target 的下标「应插入位置的前驱」求末次出现、范围统计
js
// 左边界返回的 l 不一定是 target 本身
const idx = lowerBound(nums, target);
const exists = idx < nums.length && nums[idx] === target; // 额外判断才知存在
  • 精确查找：找到返回下标，找不到返回 -1——语义清晰。
  • 左边界：返回第一个 >= target 的位置，即使 target 不存在也返回它「应该插在哪」。若所有元素都 < target，返回 n（越界，表示插末尾）。要判断 target 是否存在，需 idx < n && a[idx] === target。
  • 右边界：返回最后一个 <= target 的位置。要找 target 的末次出现，需 idx >= 0 && a[idx] === target。

范围统计技巧：[lower_bound(target), upper_bound(target)) 给出 target 出现的所有下标——左边界到「第一个 > target」之间。这是用二分做「区间计数」的标准手法。

五、写二分的统一心法 ​

死循环、溢出、退出条件、返回值——四个易错点看似零散，其实根子都在**「区间定义不自洽」**。统一心法是三步：

  1. 定区间开闭：先决定用 [l,r]、[l,r) 还是 (l,r)——这是地基。
  2. 定退出条件：由开闭推出 while 条件（闭 l<=r、半开 l<r、双开 l+1<r）。
  3. 定收缩方式：由「mid 是否可能是答案」决定——可能是答案就保留（赋给开端），确认非答案就排除（±1）；再由收缩方式决定 mid 向上还是向下取整（l=mid 配向上、r=mid 配向下）。

只要这三步自洽，二分一定对。背模板只是表象，守住循环不变量「答案必在 [l,r] 内」才是本质。

验证技巧：四 case 手推法 ​

写完二分，用四个边界 case 手推一遍，能抓住绝大多数 bug：

  • n = 1，target 就是唯一元素；
  • n = 1，target 不存在（比它小 / 比它大）；
  • target 在首元素 / 末元素位置；
  • target 比所有元素都小 / 都大。

若这四个 case 都对，二分基本就稳了。

交互演示 ​

下一步 ​

掌握了易错点与统一心法后，下一步是汇总所有模板与速查，见参考。