#153 & #154 Find Minimum in Rotated Sorted Array I, II

在一個排序過又旋轉過的陣列中找到minimum，II是允許數字重複

Concept
input陣列是排序過的，所以可以用binary search。
舉個例子來看一下

4 5 6 1 2 3

一開始start = 0, end = 5, 取出(0 + 5)/2的值 -- 6

6比start大（表示前半是按照大小排序），也比end大（違反排序，此處有旋轉），

當mid比end大時，表示最小值在mid和end之間，

就在[mid,end]範圍中找。

6 1 2 3 4 5

start比mid大，違反排序，在此範圍中繼續找。

1 2 3 4 5 6

前半和後半都符合排序，比較前半的第一個和後半的第一個，找出min。

II多了可以有duplicate的條件，

會有這種例子

10 1 10 10 10 10

此時mid和start和end都一樣，就不能用原本的方法了。

只要把後面的10都排除掉

10 1

就可以用I的方法做了。

Code

public class Solution {
    public int findMin(int[] nums) {
        /*
        mid = (start+end)/2
        if nums[starts] > nums[mid]
            min is in this range
        if nums[mid] > nums[end]
            min is in this range
        compare starts and mid, smaller one is the smallest
        */
        int start = 0, end = nums.length-1;
        int mid, min=0;
        if(nums.length == 1)
            return nums[0];
        /*handle duplicate*/            
        while (nums[end] == nums[start] && end > start) {
            end--;
        }

        while(start<=end){
            mid = (start + end)/2;
            if(nums[start] > nums[mid]){
                end = mid;
            }
            else if(nums[mid+1] > nums[end]){
                start = mid+1;
            }
            else{
                min = nums[start] < nums[mid+1] ? nums[start]: nums[mid+1];
                break;
            }
        }
        return min;
    }
}