160. Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

Notice, The array may contain duplicates.

Example Given [4,4,5,6,7,0,1,2] return 0.

Python Solutions

class Solution:
    """
    @param: nums: a rotated sorted array
    @return: the minimum number in the array
    """
    def findMin(self, nums):
        # write your code here
        if not nums:
            return -1
            
        n = len(nums)
        lo, hi = 0, n - 1
        while lo + 1 < hi:
            mid = lo + (hi - lo) / 2
            if nums[mid] == nums[hi]:
                hi -= 1
            elif nums[mid] < nums[hi]:
                hi = mid
            else:
                lo = mid
                
        if nums[lo] <= nums[hi]:
            return nums[lo]
        else:
            return nums[hi]
            
        # Total Runtime: 554 ms
        # 100% test cases passed.