算法面试：如何用二分查找目标值的首尾位置？

题干与适用场景

给定一个按非递减顺序排列的整数数组 nums 和整数 target，返回 target 在数组中的第一个和最后一个 下标；若目标值不存在，返回 [-1, -1]。数组可以为空，可以包含重复值，函数不得修改输入。要求时间复杂度 为 O(log n)，额外空间为 O(1)。

例如，nums = [1, 2, 2, 2, 3] 且 target = 2 时返回 [1, 3]；target = 4 时返回 [-1, -1]。线性扫描当然能得到答案，但最坏时间是 O(n)，不满足题目要求。

这道题适合软件工程师和算法岗位的编码轮。Amazon 当前的 SDE II 面试指引要求写出语法正确、可扩展、 健壮且经过边界验证的代码；LeetCode 也保留了同一核心问题。真正的考点不是记住两个模板，而是能否先写出 搜索边界的精确定义，再让循环条件、区间更新和返回值都服从同一个不变量。

面试官考察点

首先看候选人是否识别到“找到任意一个目标值”还不够。普通二分查找在遇到相等值时立即返回，无法保证它是 最左或最右位置；找到后再向两边线性扩展，在数组全部等于目标值时仍会退化为 O(n)。

第二个考点是边界语义。推荐把问题拆成两个插入点：

• lowerBound：第一个大于等于 target 的位置。
• upperBound：第一个严格大于 target 的位置。

Python 官方 bisectleft 和 bisectright 使用相同分区定义。只要这两个位置正确，目标存在时答案就是 [lowerBound, upperBound - 1]。

第三个考点是循环不变量。使用半开区间 [left, right) 时，空数组自然表示为 [0, 0)；循环结束条件是 left === right。如果代码混用闭区间和半开区间，例如把 right 初始化为 nums.length，却又访问 nums[right]，就会产生越界或死循环。

最后看验证能力。强回答会覆盖空数组、单元素、全部重复、目标小于最小值、目标大于最大值、目标位于两端和 目标不存在，还会说明为什么 target + 1 不是通用的 upper bound 写法：它依赖离散数值的“后继”， 会在最大安全整数处构造出约束域外的值，也无法直接推广到字符串或自定义比较器。

回答前需要澄清的问题

• 数组是否已经排序？ 本题保证非递减。如果未排序，必须先排序并保留原下标，整体就不再是 O(log n)。
• 返回原数组下标还是排序后下标？ 本题输入已排序，二者相同；若允许先排序，这会改变数据结构。
• 目标不存在时返回什么？ 本题固定返回 [-1, -1]，不能把插入点误当成命中位置。
• 允许重复值吗？ 允许，而且重复值正是需要边界二分的原因。
• 数组可以为空吗？ 可以。半开区间实现无需单独访问首尾元素，能自然返回未命中。
• 数值范围是什么？ 使用 JavaScript 安全整数。实现不计算 target + 1，因此不会为了搜索边界构造约束域外的哨兵。
• 是否必须手写二分查找？ 面试题要求手写；生产代码若标准库契约完全匹配，应优先复用标准库。
• 能否修改数组？ 不能，也不需要。两个搜索都只读取数组。

30 秒回答框架

“我会做两次边界二分，而不是找到一个目标后线性扩展。lowerBound 在半开区间 [left, right) 中找第一个 大于等于 target 的位置；upperBound 找第一个严格大于 target 的位置。循环中用 middle = left + floor((right - left) / 2)。若中点仍在目标左侧，就令 left = middle + 1， 否则收缩 right = middle。先检查 lower bound 是否越界或不等于目标；存在时返回 [lower, upper - 1]。两次搜索都是 O(log n)，额外空间 O(1)。”

分步骤深入解答

第一步：把“首尾位置”改写为两个分区点。

对 nums = [1, 2, 2, 2, 3] 和 target = 2：

lowerBound = 1  // 第一个 nums[i] >= 2
upperBound = 4  // 第一个 nums[i] > 2
answer = [1, 4 - 1] = [1, 3]

这种定义比“继续往左找”和“继续往右找”更容易验证。目标不存在时，两个插入点仍有意义。例如 target = 4 时二者都等于数组长度 5，但这不代表目标存在，因此必须单独检查 nums[lower] === target。

第二步：固定半开区间不变量。

lowerBound 在每轮开始时维持：

1. 所有下标小于 left 的值都严格小于 target。
2. 所有下标大于等于 right 的值都大于等于 target。
3. 尚未确定的候选区间是 [left, right)。

初始时 left = 0、right = nums.length，区间外没有元素，不变量成立。若 nums[middle] < target， 中点及其左侧都不可能是答案，因此令 left = middle + 1。否则中点可能就是第一个合格位置，不能丢掉， 所以令 right = middle。

每轮都严格缩短区间。当 left === right 时没有未确定元素；左侧全部小于目标，右侧全部大于等于目标， 因此这个位置就是第一个大于等于目标的位置。

upperBound 使用同一框架，只把分区条件改成：

1. 所有下标小于 left 的值都小于等于 target。
2. 所有下标大于等于 right 的值都严格大于 target。

因此当 nums[middle] <= target 时移动 left，否则收缩 right。

第三步：实现两个边界函数。

function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

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

  return left;
}

function upperBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

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

  return left;
}

两段代码只有比较条件不同。保留两个有明确名字的函数比传入一个难读的布尔开关更适合面试解释，也避免 为了单一调用提前抽象复杂的通用框架。

中点写成 left + floor((right - left) / 2)，不会先把两个大下标相加。JavaScript 数组长度受运行时 限制，本题通常不会触发数值溢出，但这种写法可以直接迁移到固定宽度整数语言。

第四步：组合结果并验证目标真的存在。

function searchRange(nums: number[], target: number): [number, number] {
  const first = lowerBound(nums, target);

  if (first === nums.length || nums[first] !== target) {
    return [-1, -1];
  }

  return [first, upperBound(nums, target) - 1];
}

检查顺序很重要。先判断 first === nums.length，再读取 nums[first]，避免把数组末尾之外的位置当成元素。 一旦确认 first 命中，upperBound 必定至少为 first + 1，所以减一后得到最后一个目标值下标。

不要用 lowerBound(nums, target + 1) - 1 代替 upper bound。在本题的安全整数约束下，它可能得到正确 结果，但当 target 是 Number.MAXSAFEINTEGER 时，加一已经超出保证精确整数运算的约束域；若输入 扩展到任意 JavaScript Number，相邻整数还可能因精度合并。字符串、BigInt 或自定义比较器也没有统一的 “下一个值”。直接搜索第一个严格大于目标的位置才是完整语义。

第五步：证明复杂度。

每次循环把候选区间从长度 k 缩到至多约 k / 2，所以每个边界函数执行 O(log n) 次比较。两次搜索 的总时间仍是 O(log n)。算法只保存常数个下标，额外空间是 O(1)，也不会修改输入数组。

若先找到任意目标再向两边扫描，[2, 2, ..., 2] 会扫描全部 n 个元素，最坏时间变为 O(n)。 若使用哈希表预处理，单次查询可以很快，但建表需要 O(n) 时间和空间；它只适合对同一静态数组执行大量 查询，而且会浪费输入已经有序这一条件。

第六步：用边界与随机差分验证。

至少覆盖：

再随机生成含重复值的排序数组，把结果与线性基准 indexOf、lastIndexOf 比较。线性方法不满足目标复杂度， 却很适合作为测试 oracle。固定用例检查已知边界，随机差分更容易暴露只在特定重复长度或端点出现的错误。

高质量示范回答

“数组已经按非递减顺序排列，而且要求 O(log n)，所以我不会先找到一个目标再向两侧扫描，因为全是重复值 时会退化成线性时间。我把答案定义成两个插入点：第一个大于等于目标的位置，以及第一个严格大于目标的位置。

两个搜索都使用半开区间 [left, right)。找左边界时，循环保持 left 左侧都小于目标，right 及其右侧 都大于等于目标。若中点值小于目标，答案只能在右侧，令 left = middle + 1；否则中点仍可能是答案， 令 right = middle。结束时二者相等，就是 lower bound。upper bound 只把条件改成中点值小于等于目标时 向右移动。

我先求 lower bound。如果它等于数组长度，或对应元素不等于目标，就返回 [-1, -1]。否则右边界是 upper bound 减一。这样空数组、目标不存在、全部重复以及目标位于首尾都使用同一套逻辑。

每次循环把区间减半，做两次仍是 O(log n)，只用常数下标，所以空间 O(1)。我会用固定边界用例，再用 随机排序数组和 indexOf、lastIndexOf 做差分测试。实现中不使用 target + 1，避免构造约束域外的 哨兵，也让边界定义适用于其他有序比较域。”

常见错误

• 找到任意目标后向两边扫描 → 全部元素相同时退化为 O(n) → 分别二分 lower bound 与 upper bound。
• 相等时立即返回 → 返回的是任意命中，不保证首尾位置 → 相等时继续保留可能包含边界的一半。
• 把 right 初始化为数组长度却访问 nums[right] → 半开区间右端不可访问 → 只访问 middle，循环到左右相等。
• 更新为 left = middle → 两元素区间可能永远不缩小 → 排除中点时使用 middle + 1。
• 目标不存在时直接返回插入点 → 插入位置不等于命中位置 → 检查越界和 nums[first] !== target。
• 用 target + 1 求右边界 → 依赖约束域外或不存在的后继值 → 直接实现第一个严格大于目标的位置。
• 混用闭区间与半开区间模板 → 初始化、循环条件和更新规则相互冲突 → 先写区间语义和不变量，再写代码。
• 只测试中间有多个重复值 → 空数组、端点和未命中仍可能错误 → 加入边界表和随机差分测试。
• 声称排序后再二分仍是 O(log n) → 排序本身至少主导总成本 → 使用题目已排序前提，未排序时重新计算复杂度。

追问及应对

追问一：如果只需要判断目标是否存在，还需要两次二分吗？

不需要。执行一次 lower bound，再检查位置是否越界且值等于目标即可，仍是 O(log n)。如果标准库提供 契约明确的二分搜索，也可以直接使用。两次搜索只为同时得到重复区间的左右边界。

追问二：如何返回目标值出现的次数？

若目标存在，次数是 upperBound - lowerBound；不存在时两个插入点相等，差也是 0。因此只计算次数时甚至 不需要单独读取数组元素。这个公式来自两个边界之间恰好都是等于目标的元素。

追问三：如果数组按降序排列怎么办？

不变量和比较方向都要反转。降序 lower bound 可以定义为第一个小于等于目标的位置，另一边界是第一个严格 小于目标的位置。不能只把最终数组倒序理解而保留原比较条件；更稳妥的方式是先写清分区谓词，再按谓词真假 更新区间。

追问四：如果元素是对象，要按某个字段查找怎么办？

把比较值抽成已排序的键，例如按 createdAt 排序就比较该字段。若键提取昂贵并会重复查询，可预先保存键 数组；Python 官方文档也建议在循环查询中缓存或预计算键。前提是对象序列在搜索期间不能被修改，否则有序 不变量失效。

追问五：如果数据不在内存，而在支持有序索引的数据库中呢？

不要把应用层二分翻译成多次远程查询。让数据库索引处理范围定位，例如查询等于目标的最小和最大稳定排序键， 或使用有序索引的起止扫描。应用层每轮一次网络往返会把 O(log n) 比较变成多次高延迟请求，也可能在并发 写入下观察到不同快照。

追问六：如何把这个模板推广到“最小可行答案”问题？

先找到一个单调谓词，例如容量 x 以下不可行、从某个位置开始都可行，然后用 lower bound 搜索第一个 谓词为真的位置。此时数组元素可以是隐式答案空间，nums[middle] < target 被替换为 !feasible(middle)。 必须先证明谓词只有一次从假变真；若真假交替，二分查找没有正确性基础。