有序数组目标值范围查找的时间复杂度：最坏情况是否为O(N)？

题目要求 #

给定非降序排列的整数数组nums，找出目标值target的起始和结束位置；若target不存在则返回[-1, -1]，且算法的时间复杂度需为O(log n)。

我的疑问与解法 #

我基于二分查找实现了如下解法，但不确定命中目标值后内部的额外while循环是否会让算法在最坏情况下的时间复杂度变为O(N)？比如输入数组为[8,8,8,8,8,8,8]、目标值为8时，命中目标后需遍历整个数组，此时时间复杂度应为O(N)，对吗？

有趣的是，该解法的运行速度超过了95%的提交，但我认为LeetCode的评测可能存在问题！

实现代码 #

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = 0
        right = len(nums) - 1
        pos = [-1,-1]
        
        while left <= right:
            middle = (left + right) // 2
            """
                This is pure binary search until we hit the target. Once
                we have hit the target, we expand towards left and right
                until we find the number equal to the target. 
            """
            if nums[middle] == target:
                rIndex = middle
                while rIndex + 1 < len(nums) and nums[rIndex + 1] == target:
                    rIndex += 1
                pos[1] = rIndex
                
                lIndex = middle
                while lIndex - 1 >= 0 and nums[lIndex - 1] == target:
                    lIndex -= 1
                pos[0] = lIndex
                break
                    
            elif target > nums[middle]:
                left = middle + 1
            else:
                right = middle - 1
                
        return pos

问题解答 #

你的判断完全正确，这种写法在最坏情况下的时间复杂度确实是O(N)。当数组中所有元素都是目标值时，二分查找会在O(log n)时间内找到中间位置，但后续的左右遍历会覆盖整个数组，这部分的时间开销是O(N)，最终整体复杂度由O(N)主导，不符合题目要求的O(log n)。

至于你的解法在LeetCode上跑赢95%的提交，主要原因是：

• LeetCode的评测用例集合中极端情况（全为目标值的数组）占比不高；
• 当数组长度较小时，O(N)和O(log n)的实际运行时间差距非常小，加上Python本身的底层优化，使得你的解法在大部分测试用例中表现出色。但这并不代表算法的时间复杂度符合题目要求。

符合O(log n)复杂度的改进思路 #

要严格满足O(log n)的要求，应该用两次二分查找分别定位左边界和右边界：

1. 找左边界：当nums[mid] == target时，不停止查找，而是继续缩小右边界，直到找到最左边的目标值；
2. 找右边界：当nums[mid] == target时，继续扩大左边界，直到找到最右边的目标值。

两次二分查找的时间复杂度都是O(log n)，总复杂度仍为O(log n)，完美符合题目要求。

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