二分查找中的循环不变量是什么？如何靠不变量避免边界错误？

简化版

循环不变量就是循环过程中始终成立的约定。

二分查找容易写错，本质是没有想清楚 left、right 表示什么。

如果约定区间是闭区间 [left, right]，就要保证目标始终可能在这个闭区间内；如果约定是左闭右开 [left, right)，就不能把 right 当成有效下标访问。

面试里能讲清楚不变量，比背模板更有说服力。

详细版

二分查找常见错误包括死循环、漏掉答案、越界访问、返回值偏 1。

这些错误基本都来自模板混用。

例如闭区间模板：

while (left <= right) {
  const mid = left + Math.floor((right - left) / 2)
  if (nums[mid] < target) left = mid + 1
  else if (nums[mid] > target) right = mid - 1
  else return mid
}

这里的不变量是：如果目标存在，它一定在 [left, right] 里。

而 lower_bound 模板：

while (left < right) {
  const mid = left + Math.floor((right - left) / 2)
  if (nums[mid] >= target) right = mid
  else left = mid + 1
}

这里的不变量是：答案始终在 [left, right] 中，right 不一定是已经检查过的元素，而是候选边界。

只要每次更新都维护不变量，二分就不会乱。

完整版教学

1. 为什么二分查找看起来简单却容易错

很多人背了好几个二分模板：

while (left <= right)
while (left < right)
right = mid
right = mid - 1

但真正写题时，一混用就会出 bug。

原因是模板背后有不同的不变量。

二分的重点不是 mid 怎么算，而是每一步更新后，答案是否仍然被保留在候选区间里。

2. 什么是循环不变量

循环不变量是指：循环开始前成立，每次循环后仍然成立，循环结束时能推出答案。

对二分来说，不变量通常描述候选区间。

模板类型	区间含义	典型循环条件	右边界更新
普通查找	目标若存在就在 `[left,right]`	`left <= right`	`right = mid - 1`
lower_bound	第一个可行答案在 `[left,right]`	`left < right`	`right = mid`
左闭右开	目标若存在就在 `[left,right)`	`left < right`	`right = mid`

不同模板可以都正确，但不能混搭。

3. 闭区间普通查找的不变量

闭区间普通查找用于找某个目标值是否存在。

function search(nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] === target) return mid
    if (nums[mid] < target) left = mid + 1
    else right = mid - 1
  }
  return -1
}

当 nums[mid] < target 时，mid 不可能是答案，左侧也不可能是答案，所以 left = mid + 1。

当 nums[mid] > target 时，mid 不可能是答案，右侧也不可能是答案，所以 right = mid - 1。

4. lower_bound 的不变量

lower_bound 找的是第一个满足条件的位置。

function lowerBound(nums, target) {
  let left = 0
  let right = nums.length
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] >= target) right = mid
    else left = mid + 1
  }
  return left
}

这里 right 初始化为 nums.length，表示答案可能是数组末尾之后的插入位置。

如果 nums[mid] >= target，mid 可能就是第一个满足的位置，所以不能丢掉 mid，要写 right = mid。

5. 不变量如何防止死循环

二分死循环常见于区间没有变小。

例如：

while (left < right) {
  const mid = Math.floor((left + right) / 2)
  if (condition(mid)) left = mid
  else right = mid - 1
}

当 left = 3, right = 4 时，mid = 3，如果继续 left = mid，区间不会变化。

解决方式是根据你要保留哪一侧来选择上取中点或下取中点。

6. 常见面试追问

误区：只记模板，不说区间含义。 面试官追问边界时，很容易暴露模板是硬背的。
误区：闭区间和左闭右开混用。 right 是否能访问，决定了初始化和循环条件。
误区：把可能答案直接丢掉。 找边界时，满足条件的 mid 往往还可能是答案。
追问：为什么 lower_bound 返回 left？ 因为循环结束时 left == right，它就是第一个可行位置。
追问：如何检查模板是否正确？ 用长度为 0、1、2 的数组手算，最容易发现边界问题。

这些问题都可以用“不变量是否被维护”来回答。

7. 一个小型自检清单

写二分前先问自己 4 个问题：

1. left 和 right 表示闭区间还是半开区间？
2. mid 满足条件时，mid 本身还可能是答案吗？
3. 每次更新后，候选区间有没有严格缩小？
4. 循环结束时，left/right 的语义能不能推出答案？

这个清单比临场猜 +1 或 -1 稳得多。

8. 面试表达模板

可以这样说：

“我写二分时会先定义循环不变量。比如 lower_bound 中，我维护答案始终在 [left, right] 内。当 mid 已经满足条件时，它可能就是第一个可行点，所以保留 mid，令 right = mid；否则答案只能在右侧，令 left = mid + 1。这样循环结束时 left == right，返回的就是目标边界。”

简化版

详细版