# 153. Find Minimum in Rotated Sorted Array

## 問題
有一個array原本是由大到小排序過的，經過旋轉後，找出array中的最小值

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
        是 [1,2,3,4,5] rotated 3 times.

## Idea
用Binary Search
1. 每次都去去看在中間的數值
2. 如果位在中間的數值大於最右邊的數值，代表這個array有被旋轉，最小值在右邊區塊 -> `l=mid+1`
3. 如果位在中間的數值小於最右邊的數值，代表這個array沒旋轉，最小值在左邊區塊 -> `r=mid`
4. 直到做又指標不是這樣的關係 `l<r`

nums = [3,4,5,1,2]

l=0,r=4

mid = (0+4)/2 = 2
[3,4,5,1,2]
     ^mid
l=3,r=4


mid = (3+4)/2 = 3
[3,4,5,1,2]
       ^mid
l=3, r=3

>:bulb:因為如果直接排序會造成 $O(NlogN)$ 時間複雜度
>```cpp
>int findMin(vector<int>& nums) {
> ranges:: sort(nums);
> return nums[0];
>}
>```

## Solution 1
時間複雜度=O(logN); 空間複雜度=O(1)

int findMin(vector<int>& nums) {
    int n=nums.size();
    int l=0, r=n-1;

    while(l<r){
        int mid = (l+r)/2;

        if(nums[mid] > nums[r]){
            l = mid + 1;
        }else{
            r = mid;
        }

    }

    return nums[l];
}

## Solution 2
時間複雜度=O(N); 空間複雜度=O(1)

**找到結尾和起始點的接口**

nt findMin(vector<int>& nums) {
    int pivot = nums[0];

    for(int i=1; i<nums.size(); i++){
        if(pivot>nums[i]){
            return nums[i];
        }
        pivot = nums[i];
    }
    if(pivot > nums[0])return nums[0];

    return pivot;

}