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

题目链接（中等）

题目描述

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

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

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

数据范围：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

示例

示例 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]

方法一：左闭右开区间

思路及解法

要找 target 的起始和结束位置，等价于找两个边界：

1. 左边界：第一个 >= target 的下标；
2. 右边界：第一个 > target 的下标，再减一。

因为数组非递减，可以用二分查找分别求这两个位置。为了复用代码，定义一个 bound(lower)：

• lower = True：找第一个 >= target 的下标；
• lower = False：找第一个 > target 的下标。

这段代码用的是左闭右开区间 [l, r)：

• 初始化 l = 0, r = len(nums)，r 指向“不在区间内”的位置；
• 循环条件 l < r，因为 l == r 时区间为空；
• 命中时 r = mid（不是 mid - 1），因为 r 本身不包含在区间内；
• 未命中时 l = mid + 1；
• 循环结束时 l == r，l 就是第一个满足条件的位置。

代码

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def bound(lower: bool) -> int:
            l, r = 0, len(nums)
            while l < r:
                mid = (l + r) // 2
                if nums[mid] > target or (lower and nums[mid] == target):
                    r = mid
                else:
                    l = mid + 1
            return l

        left = bound(True)
        right = bound(False) - 1

        if left <= right and left < len(nums) and nums[left] == target:
            return [left, right]
        return [-1, -1]

复杂度分析

• 时间复杂度：$O(\log n)$，执行两次二分查找。
• 空间复杂度：$O(1)$，只使用常数个变量。