這題前幾年同學去面試Synology的時候有被問到類似
（rotated之後找特定數字）
難易度差不多吧，就是變形的binary search
然後要注意的可能是shift一整圈的特例
[1,2,3,4,5]=>[1,2,3,4,5] 這種mid怎麼算都是會比左邊大
所以第一個if先判斷頭尾的關係
後面是判斷mid跟左邊或右邊比
mid比左邊大就移動l (代表[l,mid]之間都是ascend)
反之就移動r
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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]; } }; |
