在排序数组中查找元素的第一个和最后一个位置

446 字

2 分钟

在排序数组中查找元素的第一个和最后一个位置

2025-08-06

Algorithms

数组

/

二分查找

题目描述#

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

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

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

解题思路#

二分查找左边界：
- 查找第一个 ≥ target 的位置，若该值等于 target 则为左边界。
二分查找右边界：
- 查找第一个 > target 的位置，减一后若等于 target 则为右边界。
边界检查：
- 若左边界无效或值不匹配，返回 [-1, -1]。

关键洞察#

两次二分：
- 左边界 = 首个等于 target 的位置（lower_bound）。
- 右边界 = 首个大于 target 的位置减一（upper_bound - 1）。
统一框架：
- 两次查找均用 左闭右闭 区间，通过 mid 比较调整指针。
提前终止：
- 左边界未找到时，无需查右边界。

复杂度分析#

时间复杂度：O(log n) 两次独立的二分查找，每次 O(log n)。
空间复杂度：O(1) 仅用常数额外空间存储指针。

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @param {number} target
4
 * @return {number[]}
5
 */
6
var searchRange = function (nums, target) {
7
    const search = (nums, target, leftRight) => {
8
        let ans = -1;
9
        let left = 0, right = nums.length - 1;
10
        while (left <= right) {
11
            const middle = left + Math.floor((right - left) / 2);
12
            if (nums[middle] === target) {
13
                ans = middle;
14
                leftRight ? right = middle - 1 : left = middle + 1;
15
            } else if (nums[middle] < target) {
16
                left = middle + 1;
17
            } else {
18
                right = middle - 1;
19
            }
20
        }
21

22

23
        return ans;
24
    }
25
    return [
26
        search(nums, target, true),
27
        search(nums, target, false)
28
    ]
29
};