Leetcode 题目解析之 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.

数列基本有序，使用二分查找。分为3种情况：

假设数列是n，s是起始下标，e是最后下标，m是中间元素下标。

ns < ne

0 1 2 4 5 6 7

这种情况，直接返回ns。因为数列是有序的，或者只是旋转过一次。如果ns < ne，则表明没有旋转。最小元素是ns。

nm > ns > ne

4 5 6 7 0 1 2

只需要满足nm > ns即可，因为第一种情况排除后，ns就一定会 > ne。

在本例中：

ns = 4

nm = 7

ne = 2

则最小值肯定在7之后，到2之间，即 m+1, e。

nm < ne < ns

6 7 0 1 2 4 5

nm < ne，在本例中：

ns = 6

nm = 1

ne = 5

则表明，从m到e，数组已经是上升的，所以最小值在s, m。

    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.min(nums[0], nums[1]);
        }
        int s = 0, e = nums.length - 1;
        int m = (s + e) / 2;
        if (nums[s] < nums[e]) {
            return nums[s];
        }
        if (nums[m] > nums[s]) {
            return findMin(Arrays.copyOfRange(nums, m + 1, e + 1));
        }
        return findMin(Arrays.copyOfRange(nums, s, m + 1));
    }