Rotated Array

Suppose a sorted array A 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 will not contain duplicates.

思路：

我们要找到的pivot有如下性质:
prev > pivot < next，同时他是array里最小的

我们可以根据这个来binary search:
case 1: 
low <= high，此时low就是最小的数，即pivot
case 2:
prev > mid < next，找到pivot
case 3:
mid <= high，pivot在左边，因为prev更小
case 4:
mid > high( low > high ), pivot在右边，因为next更小

Solution:

Time: O(logn)
Space: O(1)

public class Solution {
    // DO NOT MODIFY THE LIST
    public int findMin(final List<Integer> a) {
        int left = 0;
        int right = a.size() - 1;
        int n = a.size();
        while (left <= right) {
            int lVal = a.get(left);
            int rVal = a.get(right);
            int mid = left + (right - left) / 2;
            int next = (mid + 1) % n;
            int prev = (mid + n - 1) % n;
            int mVal = a.get(mid);
            if (lVal <= rVal) {
                return lVal;
            } else if (a.get(prev) >= mVal && mVal <= a.get(next)) {
                return mVal;
            } else if (mVal <= rVal) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

如果array里有duplicate，那么当mVal == rVal或者mVal == lVa的时候，我们不能简单的将另外半边去掉，只能将一个element去除

Time: O(n)
Space: O(1)

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int n = nums.length;
        while (left <= right) {
            int lVal = nums[left];
            int rVal = nums[right];
            int mid = left + (right - left) / 2;
            int next = (mid + 1) % n;
            int prev = (mid + n - 1) % n;
            int mVal = nums[mid];
            if (lVal < rVal) {
                return lVal;
            } else if (nums[prev] > mVal && mVal <= nums[next]) {
                return mVal;
            } else if (mVal < rVal) {
                // 2 2 1 2 2 2 3
                right = mid - 1;
            } else if (mVal == rVal) {
                // 3 3 3 3 3 1 3
                right --;
            } else if (lVal < mVal) {
                // 2 2 2 3 1 1 2  
                left = mid + 1;
            } else { // (mVal == lVal)
                // 3 3 1 3 3 3 3
                left ++;
            }
        }
        return nums[0];
    }
}