153. Find Minimum in Rotated Sorted Array (https://leetcode.com/problems/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.

153. Find Minimum in Rotated Sorted Array (#1 Binary search).java

// Binary search solution: min always lies in the rotated half
// Time: O(logn), 0ms
// Space: O(1), 38.2mb
class Solution {
    public int findMin(int[] nums) {
        // Corner case: 1 element
        if(nums.length == 1) {
            return nums[0];
        }
        
        int begin = 0, end = nums.length - 1;
        while(begin < end - 1) { // At least 3 elements in the range
            int mid = begin + (end - begin) / 2;
            
            if(nums[begin] < nums[mid] && nums[mid] < nums[end]) {
                // If the array is sorted, return the first one
                return nums[begin];
            } else if(nums[begin] > nums[mid] && nums[mid] < nums[end]) {
                // If the first one is rotated, focus on that half
                end = mid;
                // Always keep the mid in the range because it can be the min
            } else { // nums[begin] < nums[mid] && nums[mid] > nums[end]
                // If the second one is rotated, focus on that half
                begin = mid;
            }
        }
        
        // begin == end - 1, only 2 elements in the range
        return Math.min(nums[begin], nums[end]);
    }
}