# 153 Find Minimum in Rotated Sorted Array

一個向右rotate若干element的sorted array，找出最小值。

Concept:

這題可以從頭跑到尾解掉，但題目的目的是要我們用binary search。

列出幾個可能性觀察一下

1234 567 7123 456 6712 345 4567 123

發現每次切半後，如果nums[start] > nums[mid]或nums[mid] > nums[end]，最小值就在那一半邊，

如果切半後兩邊都是照順序排好的，那就比較nums[start]和nums[mid]，比較小的就是最小值了。

Note: 這題讓我卡了比較久的部分是區間要取mid+1還是-1。最後結論：因為(start+end)/2是會自動捨去，所以要取的區間是[start,mid]和[mid+1,end]。

Pseudocode:

mid = (start+end)/2
while starts<=end
    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

Code:

public class Solution {
    public int findMin(int[] nums) {

        int start = 0, end = nums.length-1;
        int mid, min=0;
        if(nums.length == 1)
            return nums[0];
        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;
    }
}