二分查找为什么会溢出或死循环？mid 和边界更新有哪些坑？

简化版

二分查找常见坑有两个：mid 计算溢出，以及边界更新导致区间不缩小。

安全写法是：

const mid = left + Math.floor((right - left) / 2)

找普通目标时，排除 mid 就用 mid + 1 或 mid - 1。

找边界时，如果 mid 仍可能是答案，就保留 mid，但要确保另一侧更新能让区间变小。

详细版

在 JavaScript 里整数溢出不像 C++/Java 的 32 位 int 那么常见，但面试仍然希望你写出通用安全模板。

(left + right) / 2 在某些语言中可能溢出，所以更推荐：

left + Math.floor((right - left) / 2)

死循环通常发生在 while (left < right) 配合 left = mid。

当只剩两个元素时，向下取整会让 mid == left，如果条件分支继续令 left = mid，区间没有变化。

处理方式有两类：

如果要保留左侧，通常用 right = mid
如果要保留右侧且写 left = mid，通常要用上取中点

关键不是死背，而是确认每次循环后区间长度减少。

完整版教学

1. 二分查找的 bug 为什么隐蔽

二分查找代码通常只有 10 行左右，但错误很难一眼看出。

因为它不是语法问题，而是边界语义问题。

一个模板在数组长度为 100 时可能表现正常，在长度为 1 或 2 时才暴露问题。

二分查找要重点检查极小规模输入，因为死循环和漏答案常常发生在最后 2 个候选值之间。

2. mid 溢出问题

在 C++ 或 Java 的 32 位整数里，如果 left 和 right 都很大：

left + right

可能超过整数上限。

更稳的写法是：

const mid = left + Math.floor((right - left) / 2)

虽然 JavaScript 使用双精度浮点数表示 Number，安全整数范围更大，但保持这个习惯有利于跨语言表达。

3. 下取中点和死循环

看这个错误写法：

function wrongLastTrue(left, right) {
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (ok(mid)) left = mid
    else right = mid - 1
  }
  return left
}

如果 left = 5, right = 6，mid = 5。

若 ok(5) 为真，执行 left = mid 后仍然是 [5, 6]，循环不会结束。

4. 上取中点的使用场景

当你要找“最后一个满足条件的位置”，并且满足时需要保留 mid，可以使用上取中点：

function lastTrue(left, right) {
  while (left < right) {
    const mid = left + Math.floor((right - left + 1) / 2)
    if (ok(mid)) left = mid
    else right = mid - 1
  }
  return left
}

当区间只剩 [5, 6] 时，mid = 6。

这样无论更新 left = mid 还是 right = mid - 1，区间都会缩小。

5. 常见边界更新对照

目标	mid 满足时	mid 不满足时	mid 取法
第一个 true	`right = mid`	`left = mid + 1`	下取中点
最后一个 true	`left = mid`	`right = mid - 1`	上取中点
普通查找	命中返回	排除 mid	下取中点

这张表背后的原则是：保留可能答案，同时让区间严格变小。

6. 常见面试追问

误区：认为 JavaScript 不溢出就随便写 mid。 面试讲算法通常希望模板具备跨语言安全性。
误区：while (left < right) 下直接写 left = mid。 下取中点时，两个元素区间可能不缩小。
误区：边界题命中后直接返回。 找第一个或最后一个时，命中只能说明找到一个可行点，不一定是边界。
追问：什么时候用上取中点？ 当保留右半边且更新可能是 left = mid 时，用上取中点避免卡住。
追问：如何快速发现死循环？ 手算 left 和 right 相邻的情况，例如 [3,4]。

这些坑都可以通过“区间是否严格缩小”来统一判断。

7. 自检方法

写完二分后，用 3 类测试验证：

const cases = [
  [],
  [1],
  [1, 3]
]

再补充目标在开头、末尾、不存在、重复值的情况。

如果长度为 2 的用例能过，死循环风险会明显降低。

8. 面试表达模板

可以这样回答：

“二分查找的两个典型风险是 mid 溢出和区间不收缩。我会用 left + (right - left) / 2 的形式计算 mid。然后根据目标定义判断 mid 是否还可能是答案：如果可能，就保留 mid；如果不可能，就用 mid + 1 或 mid - 1 排除。最后用相邻边界手算，确认不会死循环。”

简化版

详细版