把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
1、遍历数组，找到数组的最小值，时间复杂度O(n)；
2、二分查找，时间复杂度O(logn)
注意旋转数组的循环不变量，A[left]>=A[right]（这道题的数组为非递减数组，并非严格的递增数组）
特例：无旋转情况以及{0,1,1,1,1,1}旋转数组
查找过程：
旋转数组可以看成两个递增（非减）数组，通过前后两个指针left，right分别指向数组的首尾，
当满足循环不变量时A[left]>=A[right]，mid=(left+right)/2，
如果A[mid]>=A[left]，说明最小值存在mid后面部分，left=mid；
如果A[mid]>=A[right]，说明最小值存在mid前面部分，right=mid；
经过循环之后，最终left会指向第一个递增数组的最后一个数，right会指向第二个递增数组的第一个数，即最小值mid=right。
最终return A[mid];
解决特例问题：
#include <iostream>
#include <vector>
using namespace std;
int MinInOrder(int* arr,int left,int right){
int result=arr[left];
for(int i=left+1;i<=right;i++){
if(result>arr[i])
result=arr[i];
}
return result;
}
int Min(int* numbers,int length){
if(numbers==NULL || length<=0)
return -1;
int left=0;
int right=length-1;
int mid=left;
while(numbers[left]>=numbers[right]){
if(right-left==1){
mid=right;
break;
}
mid=left+((right-left)>>1);
if(numbers[left]==numbers[right] && numbers[left]==numbers[mid])
return MinInOrder(numbers,left,right);
if(numbers[mid]>=numbers[left])
left=mid;
else
right=mid;
}
return numbers[mid];
}
int main()
{
int A[]={1,0,1,1,1,1,1,1};
int len=sizeof(A)/sizeof(A[0]);
Solution s;
vector<int> nums(A,A+len);
cout<<s.minNumberInRotateArray(nums)<<endl;
cout<<Min(A,len)<<endl;
return 0;
}
http://www.nowcoder.com/books/coding-interviews/9f3231a991af4f55b95579b44b7a01ba?rp=1
AC代码：
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int len=rotateArray.size();
if(len==0)
return 0;
int left=0;
int right=len-1;
int mid=left;
//if(rotateArray[left]<rotateArray[right]);
// return rotateArray[left];
while(rotateArray[left]>=rotateArray[right]){
if(right-left==1){
mid=right;
break;
}
mid=left+((right-left)>>1);
if(rotateArray[left]==rotateArray[right] && rotateArray[left]==rotateArray[mid])
return MinInOrder(rotateArray,left,right);
if(rotateArray[mid]>=rotateArray[left])
left=mid;
else
right=mid;
}
return rotateArray[mid];
}
int MinInOrder(const vector<int> &arr,int left,int right){
int result=arr[left];
for(int i=left+1;i<=right;i++){
if(result>arr[i])
result=arr[i];
}
return result;
}
};
原文：http://www.cnblogs.com/AndyJee/p/4627647.html