题目描述
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0)
return 0;
int res =rotateArray[0];
for(int i=1;i<rotateArray.size();i++){
if(res>=rotateArray[i])
res=rotateArray[i];
}
return res;
}
};
解法二：顺序查找很简单，且比较好理解，但是没有用到旋转数组这个条件，可以用折半查找，时间复杂度是logN 。每次查找都把旋转数组平均分成两部分，通过比较当前旋转数组两端点和中间点的值，判断最小值在数组的哪一部分，从而达到缩小搜索范围的目的。
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0)
return 0;
int low = 0;
int high = rotateArray.size()-1;
int mid = (low+high)/2;
while(low<high)
{
if(rotateArray[mid] < rotateArray[low]) //如果下标low指定的数组值大于mid的数组值，那么该数组肯定是非递减的，最小值应该在low和mid之间。
high = mid;
else if(rotateArray[mid] > rotateArray[low]) //如果下标low指定的数组值小于mid的数组值，那么前半部分是非递减的，最小值肯定在后面。
low = mid;
else
low = low+1; //如果mid和low对应的数组值相等，那么下一个值就是旋转的起点，即最小值。
mid = (low+high)/2;
}
return rotateArray[low];
}
};
原文：https://www.cnblogs.com/libai123456/p/12194628.html