手帐 Blog

主题

复盘 · LC 34 在排序数组中查找元素的第一个和最后一个位置 ​

题目 ​

题意 ​

非降序数组 nums 与 target，返回 target 的起始下标与结束下标；不存在则 [-1, -1]。

  • 要求 O(log n)，不能线性扫。
  • 边界：空数组；只有一个元素；target 在两端；连续多段相同值。

涉及算法 ​

标签一句话
lower_bound第一个 ≥ target 的下标 → 左端点
upper_bound第一个 > target 的下标 → 右端点 = 该下标 - 1
开区间二分left < right，right = mid / left = mid + 1

教程对照：14 · 二分查找标准模板；与今天 35 二刷 是同一家族（35 只求插入位 = 一次 lower_bound）。

评价我的解法 ​

这是今天二分线里最标准的一档：两次开区间二分，先找第一个 ≥，再找第一个 >，右端用 left - 1。和「写两次闭区间再特判」相比，语义更干净。

我的代码（摘自 34-在排序数组中查找元素的第一个和最后一个位置/index.js）：

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

对在哪：

  1. 第一次 >=：经典 lower_bound，命中即左边界。
  2. 第二次 >：经典 upper_bound，left - 1 即右边界。
  3. right = nums.length 开区间：允许答案落到 n（表示没有 ≥ / 没有 >），再靠 nums[left] !== target 拦「不存在」。

小提醒（正确性一般仍过）：

  1. 空数组时 left === 0，nums[0] 为 undefined，!== target 成立，返回 [-1,-1]——碰巧对；更稳可先写 if (!nums.length) return [-1,-1]，或判断 left === nums.length || nums[left] !== target。
  2. 今天 35 用的是闭区间，34 用的是开区间——两种都对，面试别在同一题里混用左右收缩规则。

小结：34 可以标成过关模板；建议和 35 对照口述「同是二分，多一次 upper_bound」。

最佳题解 ​

与你的主逻辑一致，仅把「找不到」写得更显式，并抽成辅助函数便于默写：

javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  const lowerBound = (x) => {
    let left = 0;
    let right = nums.length;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (nums[mid] >= x) right = mid;
      else left = mid + 1;
    }
    return left;
  };

  const L = lowerBound(target);
  if (L === nums.length || nums[L] !== target) return [-1, -1];
  const R = lowerBound(target + 1) - 1; // 等价于 upper_bound(target) - 1
  return [L, R];
};
  • 时间 O(log n)，空间 O(1)。
  • 为何等价：第一个 > target ≡ 第一个 ≥ (target+1)（整数数组时）；抽函数后两次调用更不容易抄错条件。

关联题目 ​

题为何相关
35. 搜索插入位置只要 lower_bound
278. 第一个错误的版本同一套「找第一个满足条件」
153. 寻找旋转排序数组中的最小值今天同专题的二分变体

一句话带走 ​

34 = lower_bound 找左 + upper_bound 找右；开区间 left < right 默写稳即可。