[LeetCode] 153. Find Minimum in Rotated Sorted Array

這題前幾年同學去面試Synology的時候有被問到類似

(rotated之後找特定數字)

難易度差不多吧,就是變形的binary search

然後要注意的可能是shift一整圈的特例

[1,2,3,4,5]=>[1,2,3,4,5] 這種mid怎麼算都是會比左邊大

所以第一個if先判斷頭尾的關係

後面是判斷mid跟左邊或右邊比

mid比左邊大就移動l  (代表[l,mid]之間都是ascend)

反之就移動r

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        
        if(nums[l] < nums[r])
            return nums[l];
        
        while (l < r) {
            int m = (l + r)/ 2;
            if (nums[m] > nums[r])
                l = m + 1;
            else
                r = m;
        }
        return nums[l];
    }
    
};