LeetCode 153. Find Minimum in Ro

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

方法一：推荐用binary search. O(logn)

因为题目已经说这是一个排好序的数组，旋转得到的, 情况无非下图三种情况中的一种(大端翻折到最做边，小端翻折到最右边)：

解题思路：

还是通过左( 右)边界和中间的大小关系来得到左边或者右边有序的信息。ps:至于具体和左边界还是和右边界比这个其实无所谓，都可以。假如和右边界比较：
原数组：0 1 2 4 5 6 7
情况1： 6 7 0 1 2 4 5
情况2： 2 4 5 6 7 0 1
(1) A[mid] < A[end]：A[mid : end] sorted => min不在A[mid+1 : end]中
搜索A[start : mid]
(2) A[mid] > A[end]：A[start : mid] sorted且又因为该情况下A[end]<A[start] => min不在A[start : mid]中
搜索A[mid+1 : end]
(3) base case：
a. start = end，必然A[start]为min，为搜寻结束条件。
b. start + 1 = end，此时A[mid] = A[start]，而min = min(A[mid], A[end])。而这个条件可以合并到(1)和(2)中。

分析到这里就可以写代码了：推荐九章算法的二分模版:https://github.com/billryan/algorithm-exercise/blob/master/zh-hans/basics_algorithm/binary_search.md

  public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        if (length == 2) {
            return Math.min(nums[0], nums[1]);
        }

        int start = 0, end = length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            // 搜索A[start : mid]
            if (nums[mid] <= nums[end]) {
                end = mid;
            }
            // 搜索A[mid : end]
            else {
                start = mid;
            }
        }
        if (nums[start] <= nums[end]) {
            return nums[start];
        } else {
            return nums[end];
        }
    }