题目描述：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 note：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路：
本题的直观解法很简单，直接对数组进行一次遍历就可以找到最小值，复杂度为o(n)，但是显然这不是本题的意图所在，因为没有利用到任何旋转数组的特性。
进一步分析，如果整个数组是有序的，那我们一定会想到用二分查找o(logn)来实现。对于旋转数组，我们发现，它实际上可以划分为两个排序的子数组，而且前面数组的元素都不小于后面数组的元素，并且最小值正好就是这两个数组的分界线，由此，我们可以得出以下解决方法。
- 我们可以找到数组中间的元素。如果中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时最小元素应该位于该中间元素之后，然后我们把第一个指针指向该中间元素，移动之后第一个指针仍然位于前面的递增子数组中。
-
同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时最小元素应该位于该中间元素之前，然后我们把第二个指针指向该中间元素，移动之后第二个指针仍然位于后面的递增子数组中。
-
第一个指针总是指向前面递增数组的元素，第二个指针总是指向后面递增数组的元素。最终它们会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环结束的条件。
首先用两个指针low和high分别指向数组的第一个元素和最后一个元素，然后可以找到中间元素mid。对于这个中间元素，有以下两种情况：（1）该元素大于等于low指向的元素，此时最小的元素说明在mid的后面，可以把low=mid；（2）中间元素小于等于high指向的元素，那么最小元素在mid之前，可以high=mid。特别注意：这里不要 1或者-1，因为只有这样才能保证low始终在第一个数组，high始终在第二个数组。依次循环，当最后low和high相差1时，low指向第一个数组的最后一个，high指向第二个数组的第一个（即为我们要找的最小值）。
很明显，以上查找的时间复杂度为o(logn)。
除此之外，本题还有两个特殊情况：
- 将数组前0个元素移动到后面（相当于没有旋转，数组整体有序）。明显我们上面的分析没有包含这种情况，需要特殊处理，方法也很简单，将第一个元素和最后一个元素相比，若第一个元素小于最后一个元素，则说明最小值就是的第一个元素，可以直接返回。
-
首尾指针指向的数字和中间元素三者都相等时，无法判断中间元素位于哪个子数组，无法缩小问题规模。此时，只能退而求其次，进行顺序查找。
代码实现(c )
class solution {
public:
int minnumberinrotatearray(vector rotatearray) {
int size = rotatearray.size(); //数组长度
if(size == 0){
return 0;
}
int left = 0; //左指针
int right = size - 1; //右指针
int mid = 0; //中间指针
while(rotatearray[left] >= rotatearray[right]){ //确保旋转
if(right - left == 1){ //左右指针相邻
mid = right;
break;
}
mid = left (right - left) / 2; //计算中间指针位置
//特殊情况：如果无法确定中间元素是属于前面还是后面的递增子数组，只能顺序查找
if(rotatearray[left] == rotatearray[right] && rotatearray[mid] == rotatearray[left]){
return mininorder(rotatearray, left, right);
}
//中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面
if(rotatearray[mid] >= rotatearray[left]){
left = mid;
}
//中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面
else{
right = mid;
}
}
return rotatearray[mid];
}
private:
//顺序寻找最小值
int mininorder(vector &num, int left, int right){
int result = num[left];
for(int i = left 1; i < right; i ){
if(num[i] < result){
result = num[i];
}
}
return result;
}
};
代码实现(java)
public int minnumberinrotatearray(int [] array) {
/*
三种情况：
（1）把前面0个元素搬到末尾，也就是排序数组本身，第一个就是最小值
（2）一般情况二分查找，当high-low=1时，high就是最小值
（3）如果首尾元素和中间元素都相等时，只能顺序查找
*/
int len=array.length;
if(len==0)
return 0;
int low=0,high=len-1;
if(array[low]=array[low])
low=mid;
else if(array[mid]<=array[high])
high=mid;
if(high-low==1)
return array[high];
}
return -1;
}
public int mininorder(int [] array) { //顺序查找
int min=array[0];
for(int num:array){
if(num
代码实现(python2.7)
# -*- coding:utf-8 -*-
class solution:
def minnumberinrotatearray(self, rotatearray):
# write code here
if len(rotatearray) == 0:
return 0
left = 0
right = len(rotatearray) - 1
mid = 0
while rotatearray[left] >= rotatearray[right]:
if right - left == 1:
mid = right
break
mid = left (right - left) // 2
if rotatearray[left] == rotatearray[mid] and rotatearray[mid] == rotatearray[right]:
return self.mininorder(rotatearray, left, right)
if rotatearray[mid] >= rotatearray[left]:
left = mid
else:
right = mid
return rotatearray[mid]
def mininorder(self, array, left, right):
result = array[left]
for i in range(left 1, right 1):
if array[i] < result:
result = array[i]
return result
复杂度分析
- 时间复杂度：o(logn) 。
- 空间复杂度：o(1)。