题目链接：Find Minimum in Rotated Sorted Array

Suppose a sorted array 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.

这道题的要求是在旋转数组中找到最小值。

一道在旋转数组中搜索的题目，和Search in Rotated Sorted Array和Search in Rotated Sorted Array II同样在旋转数组中搜索的题目，不过这个找最小值相对于找指定元素会容易些吧。

可以注意到最小元素num[i]一定会小于num[i-1]（如果i>0的话）。当然如果数组旋转0步（即没旋转），那么最小元素就是最左面元素了。。。可以将数组分成2个都是递增的部分（如果旋转0步，那么左部分长度为0），那么右部分的第一个元素就是最小元素了。

假设数组为[6, 7, 8, 1, 2, 3, 4, 5]，那么分成2部分后，左部分为[6, 7, 8]，右部分为[1, 2, 3, 4, 5]，则最小元素为右部分的第一个元素1。

令数组最左端元素为num[l]，最右端元素为num[r]。如果数组旋转0步，那么num[l]<num[r]，那么返回num[l]即可；否则，num[l]一定大于num[r]。假设m为l和r之间的中间元素，那么可以比较num[m]和num[r]：

  • 如果num[m]大于num[r]，那么说明num[l, …, m]均大于num[r]，因为num[l]大于num[r]而且num[l, …, m]递增。因此最小值在num[m+1, …, r]中，可令l等于m+1。
  • 如果num[m]不大于num[r]，那么说明num[m+1, …, r]均大于num[m]。因此最小值在num[l, …, m]中（注意：这部分包含m哦），可令r等于m。

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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