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.

Solution1：二分查找

思路： Always the MIN find in the rotated part

屏幕快照 2017-09-04 下午3.37.15.png

Time Complexity: O(logN) Space Complexity: O(1)

Solution2：Binary Search Template Round1

加corner case对于没有rotated的情况

Solution1 Code：

class Solution {
    public int findMin(int[] nums) {
        int start = 0, end = nums.length - 1;
        
        while (start < end) {
            // for un-rotated array
            if (nums[start] < nums[end])
                return nums[start];
            
            int mid = (start + end) / 2;
            
            // always find in the rotated part
            if (nums[mid] >= nums[start]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        
        return nums[start];
    }
}

Solution2 Code：

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