LeetCode——153. Find Minimum in Rotated Sorted Array

题目描述

首先肯定使用的是二分查找，我们首先获取中间元素的值，A[mid]，mid = (start + stop) / 2。因为数组没有重复元素，那么就有两种情况：

• A[mid] > A[start]，那么最小值一定在右半区间，譬如[4,5,6,7,0,1,2]，中间元素为7，7 > 4，最小元素一定在[7,0,1,2]这边，于是我们继续在这个区间查找。

• A[mid] < A[start]，那么最小值一定在左半区间，譬如[7,0,1,2,4,5,6]，这件元素为2，2 < 7，我们继续在[7,0,1,2]这个区间查找。

具体解决代码如下：

public class Solution {
    public int findMin(int[] nums) {
        int result = 0;
        if (nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.min(nums[0], nums[1]);
        } else {
            return find(nums, 0, nums.length - 1);
        }
    }

    public int find(int[] nums, int start, int stop) {
        if (nums[start] < nums[stop]) {
            return nums[start];
        }
        if (stop - start == 1) {
            return Math.min(nums[start], nums[stop]);
        } else {
            int middle = (start + stop) / 2;
            if (nums[middle] > nums[start]) {
                return find(nums, middle, stop);
            } else {
                return find(nums, start, middle);
            }
        }
    }
}