再看二分查找：边界到底应该怎么写？

二分查找的想法很简单：每次排除一半候选区间。但真正动手写时，最容易出错的往往也是它。

left < right 还是 left <= right？更新右边界时是 mid 还是 mid - 1？这些写法都可能正确，前提是先说清楚区间的含义。

先确定要找什么

本文只解决一个问题：在一个升序数组中，找到第一个大于或等于目标值的位置。如果不存在，就返回数组长度。

这个定义也叫 lower_bound。例如，在 [1, 3, 3, 5, 8] 中查找 3，答案是下标 1；查找 4，答案是下标 3；查找 9，答案是 5。

把目标定义得足够精确，后面的边界就不再需要凭感觉。

用半开区间描述候选范围

令候选元素区间为 [left, right)，初始状态是 [0, nums.length)。

循环过程中，始终保持两个条件：

left 左边的所有元素都小于 target。
right 及其右边的所有元素都大于或等于 target。

这两个条件就是不变量。它们说明答案只能出现在 left 到 right 之间，最终两者相遇时，位置自然确定。

一份可以解释清楚的代码

/**
 * 找到升序数组中第一个不小于目标值的位置。
 * @param nums 已按升序排列的数字数组，可包含重复元素。
 * @param target 要查找的目标值。
 * @returns 首个满足条件的下标；不存在时返回数组长度。
 */
function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    // 取中点时保留整数下标，搜索范围使用左闭右开的区间。
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] < target) {
      // 中点及其左侧都不可能是答案，可以全部排除。
      left = mid + 1;
    } else {
      // 中点仍可能是第一个符合条件的位置，将其作为新的右边界。
      right = mid;
    }
  }

  return left;
}

注意代码中没有使用位运算计算中点。JavaScript 的位运算会把数值转换为 32 位有符号整数，在讨论通用索引时，Math.floor 的意图更直接。

手动检查几个边界

输入数组	目标值	返回下标	含义
`[]`	`3`	`0`	空数组，插入位置为零
`[3]`	`3`	`0`	第一个元素即符合条件
`[1, 3, 3, 5]`	`3`	`1`	找到重复值的第一个位置
`[1, 3, 5]`	`4`	`2`	返回第一个更大的元素位置
`[1, 3, 5]`	`8`	`3`	不存在符合条件的元素

时间复杂度是 O(log n)，额外空间是 O(1)。不过比复杂度更值得记住的是：每次循环都缩短候选范围，同时保持不变量成立。

不必背很多模板

以前总想着把每种写法都记牢，后来发现更实用的办法是固定一种语义，遇到新题再把问题转成同一种形式。

先问自己三件事：我在找什么？区间代表什么？这次更新为什么不会丢掉答案？

能解释清楚这三件事，代码往往也就写对了。