LeetCode153 Find Minimum in Rotated Sorted Array


描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

样例

1
2
3
4
Input:
[4, 5, 6, 7, 0, 1, 2]
Output:
0

思路

递增的原始数组(没有重复的元素),经过某个中枢元素旋转后,得到一个新的数组。现在只给出新数组,求其中最小的元素。

直接遍历新数组,就可以找到最小的元素,复杂度$\mathcal{O}(n)$,但这显然不是我们想要的。

由于原始数组单调,不妨考虑二分,但是怎么更新$l$和$r$呢?

如果此时位于$mid$的元素大于位于$r$的元素,那么说明$mid$正位于中枢元素的左侧(中枢元素就是0),即$[l, mid]$这一段区间都不可能是答案,于是更新l = mid + 1

反之,说明$mid$位于中枢元素的右侧(或者就是中枢元素本身),于是更新r = mid

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] > nums[r]) l = m + 1;
else r = m;
}
return nums[l];
}
};