二分查找的边界之美：从循环模板到不变式

二分查找大概是写错率最高的基础算法。left < right 还是 left <= right、mid + 1 还是 mid，每次都要重新想一遍。这篇用「不变式」的思路统一梳理。

一个统一的模板

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

这个写法返回第一个 >= target 的下标（即 lower_bound）。如果 target 大于所有元素，返回 nums.length。

把边界画在数轴上

核心是想清楚循环结束时 left 和 right 的位置关系：

• 循环条件 left <= right：退出时 right = left - 1，答案落在 left；
• 循环条件 left < right：退出时 left = right，需要根据题意判断返回哪一个。

画一条数轴，标出每个分支收缩的是哪一侧，答案落点就非常直观，不需要死记硬背。

mid 的取值

left + (right - left) / 2 而不是 (left + right) / 2，是为了防止两数相加溢出。JavaScript 的 number 不会溢出，但这是从 C/Java 时代继承下来的好习惯，而且能提醒你：mid 永远偏向 left 一侧。

小结

二分的本质不是「每次砍一半」，而是维护一个不变式：目标答案始终在 [left, right] 区间内。写代码前先在数轴上验证不变式，边界就不会错。