153. Find Minimum in Rotated Sorted Array (Binary Search) 20.2.11 Medium

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

Solution: --------------------------------------------------------------------- Binary Search
----------------------------------------- O(logn) T, O(1) S
class Solution(object):
    def findMin(self, nums):
        if nums[len(nums) - 1] > nums[0] or len(nums) == 1:  # Eliminate the case when the array is already sorted
                                                             # or the array only has one element
            return nums[0]
        left, right = 0, len(nums) - 1
        while(left <= right):
            middle = (left + right) / 2
            if nums[middle] < nums[middle - 1]:
                return nums[middle]
            if nums[middle] > nums[middle + 1]:           # To copy with situation like [2, 1]
                return nums[middle + 1]                   # We need to consider both num[middle + 1] and nums[middle] to be the minimum
            '''
            Find the mid element of the array.
            If mid element > first element of array this means that we need to look for the inflection point on the right of mid.
            If mid element < first element of array this that we need to look for the inflection point on the left of mid.
            '''
            if nums[middle] > nums[0]:                    # THE KEY for every binary search problem is how we should 
                                                          # update the left and right pointer
                                                          # In this example, this is also the MOST IMPORTANT PART !!!!!!!!!!!!!!!!!
                                                          # if nums[middle] > nums[0], then the upper half must be sorted,
                                                          # so we should focus on the latter half and assign left to mid + 1
                                                          # and vice versa.
                left = middle + 1
            elif nums[middle] < nums[0]:
                right = middle - 1
        """
        :type nums: List[int]
        :rtype: int
        """


Java Version:
class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        if (nums[nums.length - 1] > nums[0] || nums.length == 1) {
            return nums[0];
        }
        
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid + 1 < nums.length && nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (mid - 1 >= 0 && nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (nums[left] > nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}