I was going through LeetCode problem 34. Find First and Last Position of Element in Sorted Array, which says:

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.

Since the question wanted logn run-time, I implemented the binary-search logic. But I am not sure, and think that, with the extra-while loop inside the base condition, I actually go to O(n) in the worst case. Is that true?

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

Here is what I think for an example array that looks like:

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

When the base condition nums[middle] == target hits, I will need to iterate the complete array and this makes it run-time complexity as O(n), right?

Interestingly, this solution is faster than 95% of the submissions!! But I think there is some issue with LeetCode!!!

CodePudding user response：

Yes, you are right, the loop degrades the worst case time complexity. You rightly identified what happens when the input array has only duplicates of the target value, and no other value.

The solution is to perform two binary searches: one that prefers going to the left side, and one that prefers to go to the right side of the target value.

If the test cases do not thoroughly test this O(n) behaviour, this O(n) solution will not come out as a bad one.