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.

思路：如果中间节点的值最大，则取后半部分，如果中间节点的值最小，则取前半部分。

C++实现代码如下：（采用二分法的方法，注意边界的处理）

#include<iostream>
#include<vector>
using namespace std;

class Solution
{
public:
    int findMin(vector<int> &num)
    {
        if(num.empty())
            return 0;
        int s=0;
        int t=num.size()-1;
        if(num[s]<num[t])
            return num[s];
        while(s<t)
        {
            int mid=(s+t)/2;
            if(num[mid]<num[t])
                t=mid;
            else
                s=mid+1;
        }
        return num[s];
    }
};

int main()
{
    Solution s;
    vector<int> num={4,5,6,7,8,9,0,1,2,3};
    cout<<s.findMin(num)<<endl;
}