python - 在排序数组中查找目标范围的时间复杂度——这个解决方案在最坏的情况下是 O(N) 吗？

Question

我正在经历 LeetCode 问题 34. Find First and Last Position of Element in Sorted Array ，它说:

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

由于问题需要 logn 运行时，我实现了二进制搜索逻辑。但我不确定，并且认为，在基本条件内使用额外的 while 循环，在最坏的情况下我实际上会转到 O(n)。是真的吗？

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

这是我对一个示例数组的看法:

input = [8,8,8,8,8,8,8] , target = 8

当满足基本条件 nums[middle] == target 时，我将需要迭代整个数组，这使其运行时复杂度为 O(n)，对吧？

有趣的是，这个解决方案比 95% 的提交都快!!但我认为 LeetCode 有一些问题!!!

Answer 1

是的，你是对的，循环降低了最坏情况下的时间复杂度。您正确地确定了当输入数组仅 重复目标值而没有其他值时会发生什么。

解决方案是执行两种二分搜索:一种倾向于向目标值的左侧移动，一种倾向于向目标值的右侧移动。

如果测试用例没有彻底测试这个 O(n) 的行为，这个 O(n) 的解决方案不会是一个糟糕的解决方案。