CODEWITHSUNDEEP
algorithmbinary-search
nz_21
nz_21

Reputation: 7393

Minimum in rotated sorted array with duplicates

I am trying to find the minimum in a rotated sorted array with duplicates:

I tried this:

def find_pivot(arr):
    lo = 0 
    hi = len(arr) -1 
    while lo<=hi:
        mid = (hi+lo)//2 
        if arr[mid]<arr[0]:
            hi = mid-1
        else:
            lo = mid+1
    return lo 


class Solution:
    """
    @param nums: a rotated sorted array
    @return: the minimum number in the array
    """
    def findMin(self, nums):
        pivot_index = find_pivot(nums)
        left = nums[:pivot_index]
        right = nums[pivot_index:]
        if right:
            return right[0]
        return left[0]

This fails when the array is [999,999,1000,1000,10000,0,999,999,999]. My algorithm returns 999, when it should return 0

How do I fix this?

Upvotes: 0

Views: 93

Answers (1)

ashunt
ashunt

Reputation: 64

Binary search will not work here because of duplicates.

Suppose your array is [1,1,1,1,1,0,1,1]. Then arr[lo] = arr[hi] = arr[mid] = 1: which half you dive in? You may say "right one!" of course, but why? All informations you have with those three items only is not enough to have the certainty of you choice. In fact the array could be [1,0,1,1,1,1,1,1], and yet arr[lo] = arr[hi] = arr[mid] = 1, but the pivot is not in right half now.

In the worst case, with this type of instances you stil need to scan the whole array.

If you could have a more tighten order in the array, which means no duplicates (or, no more than k duplicates) then binary search would be useful.

Upvotes: 1

Related Questions