'''
keys: 
Solutions:
Similar: 154
T:
S:
'''
from typing import List


class Solution:
    # binary search
    '''
    Classic binary search problem. Looking at subarray with index [start,end]. 
    We can find out that if the first member is less than the last member, 
    there's no rotation in the array. So we could directly return the first 
    element in this subarray.

    If the first element is larger than the last one, then we compute the 
    element in the middle, and compare it with the first element. If value 
    of the element in the middle is larger than the first element, we know 
    the rotation is at the second half of this array. Else, it is in the first 
    half in the array.
    '''
    # You use while (start <= end) if you are returning the match from inside 
    # the loop.
    # You use while (start < end) if you want to exit out of the loop first, 
    # and then use the result of start or end to return the match.
    
    def findMin1(self, nums: List[int]) -> int:
        start, end = 0, len(nums) - 1
        while start < end:
            if nums[start] < nums[end]:
                return nums[start]
            
            mid = start + (end - start)//2
            
            if nums[mid] >= nums[start]:
                start = mid + 1  # the rotation hapens in the second half
            else:
                end = mid
        return nums[start]


    # self-made
    def findMin(self, nums: List[int]) -> int:
        if not nums:
            return 
        if len(nums) == 1:
            return nums[0]
        
        def findIdx(): # find rotate idx
            l, r = 0, len(nums)-1
            if nums[l] < nums[r]:
                return 0

            while l <= r:
                mid = l + (r-l)//2
                if nums[mid] > nums[mid+1]:
                    return mid + 1

                if nums[l] <= nums[mid]: # must be <=
                    l = mid+1
                else:
                    r = mid-1 
        
        idx = findIdx()
        return nums[idx]
    
    
    
    # self-written
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        for i in range(len(nums)-1):
            if nums[i+1] < nums[i]:
                return nums[i+1]
        return nums[0]
        