153. Find Minimum in Rotated Sorted Array

1.問題

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;
    }
};