跳到主要内容

力扣34-在排序数组中查找元素的第一个和最后一个位置[二分法]

· 阅读需 5 分钟
Yana Ching
Yana Ching
Front End Engineer

原题​

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。

请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。


示例 1：

> 输入：nums = [5,7,7,8,8,10], target = 8
> 输出：[3,4]

示例 2：

> 输入：nums = [5,7,7,8,8,10], target = 6
> 输出：[-1,-1]

示例 3：

> 输入：nums = [], target = 0
> 输出：[-1,-1] :::tip
提示

  • 0 <= nums.length <= 10⁵

  • -10⁹ <= nums[i] <= 10⁹

  • nums 是一个非递减数组

  • -10⁹ <= target <= 10⁹

解题思路​

已知：

  1. 数组有序 - 定位 二分法
  2. nums
  3. target 值
  4. 有可能有重复元素

求：

  1. target 出现的第一个出现的位置
  2. target 出现的最后一个出现位置

寻找最左：

  1. 找到 mid 符合 target 之后，更新 LBoder 为 mid
  2. 将 r 移动到 mid 左边，寻找更左侧的 target
  3. 有就继续收缩，没有直接返回 -1

寻找最右：

  1. 找到 mid 符合 target 之后，更新 RBoder 为 mid
  2. 将 l 移动到 mid 右边，寻找更右侧的 target
  3. 有就继续收缩，没有直接返回 -1

明确隐藏条件：

  1. 若找不到 first，那么 last 也是不存在，因此首次判断 first 存在与否再决定是否寻找 last
  2. 当能找到 first 时，last 最小也只能是 first，不会出现 -1
  3. 检查空数组，空数组直接返回 [-1, -1]

解题过程​

  1. 初始化左右指针：left = 0, right = len(nums) - 1
  2. 二分查找第一个位置
    • 如果找到匹配的 target，将 right 指针移到中点的左侧继续查找，直到锁定第一个出现的 target。
  3. 二分查找最后一个位置
    • 如果找到匹配的 target，将 left 指针移到中点的右侧继续查找，直到锁定最后一个出现的 target。
  4. 返回结果：如果没有找到目标值，返回 [-1, -1]

复杂度​

  • 时间复杂度: O(logN)

  • 空间复杂度: O(1)

代码​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // 直接检查空数组
  const n = nums.length
  if (n === 0) return [-1, -1]

  function getFirst(nums, target, n) {
    // [l, r]
    let l = 0
    let r = n - 1
    let first = -1
    while (l <= r) {
      const mid = (l + r) >>> 1
      // 找到 target 位置后更新 first 位置，收缩右边界，继续向mid左边寻找是否有更左值
      if (target === nums[mid]) {
        first = mid
        r = mid - 1
      } else if (target > nums[mid]) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }
    return first
  }

  function getLast(nums, target, n) {
    // [l, r]
    let l = 0
    let r = n - 1
    let last = -1
    while (l <= r) {
      const mid = (l + r) >>> 1
      // 找到 target 位置后更新 last 位置，收缩左边界，继续向mid右边寻找是否有更右值
      if (target === nums[mid]) {
        last = mid
        l = mid + 1
      } else if (target > nums[mid]) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }
    return last
  }
  let first = getFirst(nums, target, n)
  // 如果找不到第一个位置，说明数组中没有这个元素，那么最后一个位置也是找不到的
  // 循环条件上理解则是 一旦 left 为 -1了，在循环条件 left <= right这个上， right也只能是 -1 了
  if (first === -1) return [-1, -1]
  // 一旦能够找到第一个位置，那么 last 最小也只能是 first
  // 循环条件上理解则是 一旦 left > 0 了，在循环条件 left <= right这个上， right也只能是 > 0 了
  let last = getLast(nums, target, n)
  return [first, last]
}