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

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

题目描述

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

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

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

核心思考：二分查找的边界收缩与越界防御

前置知识： 二分查找的基础边界处理原则，可参考 704. 二分查找。

在标准的二分查找中，当 nums[mid] == target 时会立即返回索引。但在本题中，目标值可能连续出现多次，要求求解目标区间的整段范围。为保证严格的 $O(\log n)$ 时间复杂度，我们需要执行两次独立的二分查找，分别逼近左边界与右边界。

1. 寻找左侧边界

在探索左边界时，当遇到 nums[mid] == target，不能停止搜索。此时需要收缩右边界，即隐式地认为目标区间还在更左侧，执行 right = mid - 1。这样可以在不断缩小的区间内逼近最左侧的 target。当 while 循环终止时，left 指针将停留在可能等于 target 的最左侧端点。

2. 寻找右侧边界

与寻找左侧边界同理，探索右边界并在 mid 处命中 target 时，需要收缩左边界，执行 left = mid + 1。这样能够将搜索区间锁定在右半部，进而向右逼近。循环结束时，right 指针将停留在可能等于 target 的最右侧端点。

3. 越界防御与结果校验

由于放宽了命中的跳出条件，循环完全结束后，指针存在无法命名的可能情况，必须执行严谨的越界防御校验：

• 若 target 严格大于数组内的所有元素，左边界查找中的 left 会越界递增至 len(nums)。
• 若 target 严格小于数组内的所有元素，右边界查找中的 right 会越界递减至 -1。
• 即使指针未发生物理越界，最后停留位置所指的元素也存在并非 target 的可能。

因此，在返回函数前，必须严格检查 left 或 right 指针是否游离于 0 到 len(nums)-1 的合法区间之外，并验证其对应的值是否确为 target。任意条件未被满足，均代表目标不存在，按命题要求返回 -1。

解题思路 (Python)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        def left_(nums,target):
            left = 0
            right = len(nums) - 1

            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    right = mid - 1
            if left < 0 or left > len(nums) - 1:
                return -1
            if nums[left] == target:
                return left
            else:
                return -1
        
        def right_(nums,target):
            left = 0
            right = len(nums) - 1

            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    left = mid + 1
            if right < 0 or right > len(nums) - 1:
                return -1
            if nums[right] == target:
                return right
            else:
                return -1

        return[left_(nums,target),right_(nums,target)]

复杂度分析

• 时间复杂度：$O(\log N)$，其中 $N$ 为数组空间长度。算法先后执行了两次互相独立的标准二分查找。每次查找的时间损耗均为空间折半操作对应的 $O(\log N)$，因此总体复杂度控制在对数级极限。
• 空间复杂度：$O(1)$。算法仅使用了常数个指针标量承载二分搜寻范围的状态，空间结构未随输入规模线性扩张。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

n
num1 num2 num3 ... numN
target

第一行输入数组长度 n，第二行输入 n 个整数，第三行输入目标值 target。

完整代码：

import sys

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
    if not nums:
                return [-1, -1]
            def left_(nums,target):
                left = 0
                right = len(nums) - 1

                while left <= right:
                    mid = left + (right - left) // 2
                    if nums[mid] < target:
                        left = mid + 1
                    elif nums[mid] > target:
                        right = mid - 1
                    elif nums[mid] == target:
                        right = mid - 1
                if left < 0 or left > len(nums) - 1:
                    return -1
                if nums[left] == target:
                    return left
                else:
                    return -1

            def right_(nums,target):
                left = 0
                right = len(nums) - 1

                while left <= right:
                    mid = left + (right - left) // 2
                    if nums[mid] < target:
                        left = mid + 1
                    elif nums[mid] > target:
                        right = mid - 1
                    elif nums[mid] == target:
                        left = mid + 1
                if right < 0 or right > len(nums) - 1:
                    return -1
                if nums[right] == target:
                    return right
                else:
                    return -1

            return[left_(nums,target),right_(nums,target)]

def main():
    lines = sys.stdin.read().strip().split()
    n = int(lines[0])
    nums = list(map(int, lines[1:1+n]))
    target = int(lines[1+n])

    sol = Solution()
    result = sol.searchRange(nums, target)
    for v in result:\n        print(v, end=' ')\n    print()

if __name__ == "__main__":
    main()

运行示例：

echo -e "5\n2 7 11 15\n9" | python solution.py