Find Minimum in Rotated Sorted Array

Suppose a sorted array 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.

给定一个有序的数组，不过数组通过一个支点进行了旋转，让我们从中找到最下的元素。我们如果直接找时间复杂度为O(n), 因为这是有序数组进行了旋转，我们可以考虑二分查找法，这样时间复杂度为O(logn)。二分查找的关键在于找到一个条件进行判断，然后可以省略掉一半元素。在这这题目中，我们通过中间元素与最右边的元素进行比较，如果中间元素array[m] > array[right]，那么说明做部分为有序的，并且最小值肯定在右半部分，这是我们只需要移动左指针，指向m + 1位置，然后对后半部分进行搜索。如果中间元素小于最右边元素，说明最小值在左部分，这是让右指针指向m位置，因为m位置的元素可能为最小值，然后查找左半部分。代码如下：

public class Solution {
    public int findMin(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        int l = 0; 
        int r = nums.length - 1;
        while(l < r) {
            int m = l + (r - l) / 2;
            if(nums[m] > nums[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return nums[l];
    }
}