LeetCode寻找排序数组元素首尾位置：运行时优化咨询

你的当前解法在找到目标值后用线性扫描找边界，最坏情况会退化成O(n)时间复杂度（比如数组全是target的时候），而且实际运行时间波动大。要严格满足O(log n)要求，同时提升运行效率，核心是用两次二分查找分别定位左、右边界，完全避免线性遍历。

优化思路 #

• 左边界二分：专门找第一个等于target的位置。当中间值大于等于target时，收缩右边界；否则收缩左边界。最后验证左指针是否合法且对应值为target。
• 右边界二分：专门找最后一个等于target的位置。当中间值小于等于target时，收缩左边界；否则收缩右边界。最后验证右指针是否合法且对应值为target。

优化后的代码 #

def searchRange(nums, target):
    left = -1
    # 找左边界
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2  # 用整数除法避免浮点数
        if nums[mid] >= target:
            high = mid - 1
        else:
            low = mid + 1
    if low < len(nums) and nums[low] == target:
        left = low
    
    right = -1
    # 找右边界
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1
    if high >= 0 and nums[high] == target:
        right = high
    
    return [left, right]

关键优化点说明 #

1. 时间复杂度严格O(log n)：两次二分查找，每次都是O(log n)，整体复杂度稳定在O(log n)，不会因为target重复多而变慢。
2. 避免线性扫描：去掉了原代码中从mid向两边遍历的while循环，彻底消除了最坏情况的O(n)开销。
3. 整数除法修正：原代码中mid = (high + low)/2会得到浮点数，改成//直接得到整数索引，避免类型转换的微小开销。

内容的提问来源于stack exchange，提问作者Ilia