154. Find Minimum in Rotated Sorted Array II

1.問題

2.想法

• 提問:

• function header, parameter

• test input

• 說明想法

  • 用binary search

  • 如果left < mid, 表示左半邊已排序

    • 拿最小值與最左值比較, 並繼續搜尋右邊

  • 如果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;
    }
};