Find Minimum in Rotated Sorted Array

Problem

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.

Notice

You may assume no duplicate exists in the array.

Example

Given [4, 5, 6, 7, 0, 1, 2] return 0

Note

排序数组中找最小值或最大值的题目，很明显可以使用二分法。我们先来看看rotated sorted array有哪些情况，再确定如何使用二分法：

        //LO   M   HI
        // 789123456
        // 678912345
        // 456789123
        // 123456789

上面的例子分别是较小元素，最小元素，较大元素，中位数在中点的情况。可见，用队首元素num[start]和中点num[mid]比较没有意义。因此，只判断终点和中点元素的大小关系即可。

Solution

public class Solution {
    public int findMin(int[] num) {
        int start = 0, end = num.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (num[end] > num[mid]) end = mid;
            else start = mid;
        }
        return num[start] < num[end] ? num[start] : num[end];
    }
}

Find Minimum in Rotated Sorted Array

Problem

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.

The array may contain duplicates.

Example

Given [4,4,5,6,7,0,1,2] return 0

Note

53335 x
33533 x 
55535 x
42333 x
45333 x

上面这些case是很难直接用二分法判断的，只能对中点两边同时使用二分法递归，或者完全遍历数组求最优解。
二分法递归的步骤是：建立helper()函数，当中点值大于等于末位值，夹逼到后半段，舍弃中间值；当中点值小于等于末位值，夹逼到前半段，不舍弃中间值。这里有一种情况是（上述后三个case），中点值和末位相等。此时，两边同时递归，并返回两边递归值的较小值。当首位和末位重合，说明已夹逼得到最小值。

Solution

二分法递归

public class Solution {
    public int findMin(int[] num) {
        return helper(num, 0, num.length-1);
    }
    public int helper(int[] num, int start, int end) {
        if (start == end) return num[start];
        int mid = start + (end - start) / 2;
        int left = Integer.MAX_VALUE, right = left;
        if (num[mid] >= num[end]) {
            right = helper(num, mid+1, end);
        }
        if (num[mid] <= num[end]) {
            left = helper(num, start, mid);
        }
        return Math.min(left, right);
    }
}

暴力循环

public class Solution {
    public int findMin(int[] num) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < num.length; i++) {
            min = Math.min(num[i], min);
        }
        return min;
    }
}