一、 题目
给定一个排好序的数组。数组可能是单调递增，也可能有一个变换。
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2)
要求找出最小的数。
二、 分析
这道题正如题目所说的分来两种情况
1、 严格单调递增
2、 有一个拐点
我们须要分情况处理。当然也能够无论这些直接遍历，即从头到尾扫描，找出最小的数；假设依据题意，我们须要考虑
1、 当严格单调时，因为是排好序的所以我们直接return 第一个元素就可以；或者直接利用二分法查找也能够。
2、 当有拐点时，我们就能够二分查找高速找到最小值。
综上所诉。考虑两种情况能够提高效率，可是直接当做一种情况更优点理。
并且都能通过。
class Solution {
public:
int findMin(vector<int> &num) {
int min = num[0];
for(int i=1;i<num.size();i++){
if(num[i]>num[i-1])
min = num[i];
}
return min;
}
};
class Solution {
public:
int findMin(vector<int> &num) {
if(num.size()==0) return 0;
int sta=0;
int flag;
int end=num.size()-1;
while(sta<end){
flag = (sta+end)/2;
if(num[flag]<num[end])
end=flag;
else
sta=flag+1;
}
return num[sta];
}
};
class Solution {
public:
int findMin(vector<int> &num) {
int cou=num.size()-1; //the numbers of num
if(num.size()==0) return 0; //the num is null
if(num.size()==1) return num[0]; //num have a single number
int mid=0;
int sta=0; //the start
int end=cou; //the end
if(num[sta]<num[end]) { //Monotonically increasing
return num[0];
}
else { //There are situations inflection point
while(sta<end){
mid = (sta+end)/2;
if(num[mid]<num[end])
end=mid;
else
sta=mid+1;
}
return num[end];
}
}
};