153_find_min_in_rotated_sorted_array.py

'''
153. Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order 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.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1
Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

def findMin(self, nums: List[int]) -> int:
'''


class Solution(object):
    def findMin(self, nums):
        '''
        approach
            1. use min(): TC: O(N)
            2. binary search TC: log(n)
        '''
        low, high = 0, len(nums)-1
        while low < high:
            mid = (low+high)//2
            if nums[mid] > nums[high]:
                low = mid+1
            else:
                high = mid
        return nums[low]


if __name__ == '__main__':
    # begin
    s = Solution()
    print(s.findMin([3, 4, 5, 1, 2]))