# 154. Find Minimum in Rotated Sorted Array II

## 1.問題

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LacqHh4tqA3kLVpJ2up%2F-Lacqoi_03t0sSKWOTXa%2Fimage.png?alt=media\&token=0530708c-1bb4-4aeb-a66a-e39be176f028)

## 2.想法&#x20;

* 提問:
* function header, parameter
* test input
* 說明想法&#x20;
  * 用binary search
  * 如果left < mid, 表示左半邊已排序&#x20;
    * 拿最小值與最左值比較, 並繼續搜尋右邊
  * 如果left > mid, 表示右半邊未排序
    * 拿最小值與最左值比較, 並繼續搜尋左邊

## 3.程式碼

* while loop

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

