在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

34. Find First and Last Position of Element in Sorted Array ,表示:

nums 按非降序排序,找到给定的开始和结束位置 target 价值

目标 在数组中找不到,返回 [-1, -1] .

O(log n) 运行时复杂性。

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)