I was going through LeetCode problem 34. Find First and Last Position of Element in Sorted Array, which says:
Given an array of integers
numssorted in non-decreasing order, find the starting and ending position of a given
targetis not found in the array, return
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 = rIndex lIndex = middle while lIndex - 1 >= 0 and nums[lIndex - 1] == target: lIndex -= 1 pos = 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
Interestingly, this solution is faster than 95% of the submissions!! But I think there is some issue with LeetCode!!!
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.