# 153. Find Minimum in Rotated Sorted Array

## 1.問題

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-Lac-vyvVXWLe4LgCZhw%2F-Lac08BtfdBt8ikBix3n%2Fimage.png?alt=media\&token=852a4921-75a3-4292-ae83-9d5c8a864f9e)

## 2.想法 

* 提問:
* function header, parameter
* test input
* 說明想法 
  * 用binary search
  * 如果left < mid, 表示左半邊已排序-> 左半邊的不看, mid = left
  * 如果left > mid, 表示右半邊未排序-> 右半邊的不看, mid = right

## 3.程式碼

* while loop

```
class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        
        int size = nums.size(), left = 0, right = size - 1;
        if (nums[left] > nums[right]) {
            while (left != (right - 1)) {
                int mid = (left + right) / 2;
                if (nums[left] < nums[mid]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            return min(nums[left], nums[right]);
        }
        return nums[0];
    }
};
```

* recursive

```
class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.empty()) return 0;
        return search(nums, nums[0], 0, nums.size() - 1);
    }
private:
    int search(vector<int>& nums, int res, int left, int right) {
        if (left < right - 1) {
            int mid = (left + right) / 2;
            if (nums[left] < nums[mid]) {
                res = min(res, nums[left]);
                return search(nums, res, mid, right);
            } else {
                res = min(res, nums[right]);
                return search(nums, res, left, mid);
            }
        }
        res = min(res, nums[left]);
        res = min(res, nums[right]);
        return res;
    }
};
```