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

class Solution {
    public int findMin(int[] nums) {
        int res = nums[0];
        for(int i = 0; i < nums.length-1; i++){
            if(nums[i+1] < nums[i]) return nums[i+1];
        }
        return res;
    }
}

第一个右<左的时候就是要找的。

class Solution {
    public int findMin(int[] nums) {
        // int res = nums[0];
        // for(int i = 0; i < nums.length-1; i++){
        //     if(nums[i+1] < nums[i]) return nums[i+1];
        // }
        // return res;
        if(nums.length == 1) return nums[0];
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return nums[left];
    }
}

也可以用二分法，和查找target相反，

• 若A[mid] < A[right]，则区间[mid,right]一定递增，断层一定在左边
• 若A[mid] > A[right]，则区间[left,mid]一定递增，断层一定在右边
• nums[mid] == nums[right]，这种情况不可能发生，因为数组是严格单调递增的，不存在重复元素

二分法中，似乎查找target的时候用的是left <= right, 返回nums[mid], 找最大最小数用的是left < right, 返回nums[left/right].