首页 > 代码库 > Find Minimum in Rotated Sorted Array

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;}

 

Find Minimum in Rotated Sorted Array