本题来自《剑指offer》 旋转数组中的最小数字
题目：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：
从问题本身入手，可以看出，数据局部有序，思考数据中是否重复。属于查找范畴，顺序查找肯定可以，需要O(n)时间，数据有序可以考虑二分查找为log(n)时间内。
若数据不重复：二分法查找
可以局部看成两个有序的数组A、B。p1指向首，p2指向尾：
如果中间值大于p1的值，说明最小值在B中，将p1指向中间值。
如果中间值小于p2的值，说明最小值A中，将p2指向中间值。
如果中间值和p1和p2的值相等，则采用下面的方法，顺序查找。
终止条件是，当p1和p2相邻，最小值便是p2指向的值。返回即可
若数据重复：顺序查找
假设第一个为最小的元素，开始遍历，后面凡是小于该值的便保存，最后返回。
C++ Code：
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int p1 = 0;
int p2 = rotateArray.size()-1;
int mid = p1;
while (rotateArray[p1] >= rotateArray[p2]){ //循环条件首值应该大于后值
if (p2 - p1 == 1){ //当首尾相邻时候
mid = p2; //那么最小值是p2的方向
break;
}
mid = (p1 + p2)/2; //中间值为加权平均
if (rotateArray[mid]==rotateArray[p1]&&rotateArray[mid]==rotateArray[p2]){
return minInorder(rotateArray); //如果三值相等，则采用顺序查找法
}
if (rotateArray[mid] >= rotateArray[p1]){ //如果中间值大于首值，说明最小值在后面的数组中
p1 = mid; //手指针后移
}
else if (rotateArray[mid] <= rotateArray[p2]){ //如果中间值小于末值，说明最小值在前面的数组中
p2 = mid; //将末值前移
}
}
return rotateArray[mid];
}
int minInorder(vector<int> rotateArray){ //顺序查找法为O(n)
int result = rotateArray[0]; //假设最小值是首值
for (int i = 1;i<rotateArray.size();i++){
if (result >= rotateArray[i]){ //如果当找到小于该值时候，便保存
result = rotateArray[i];
}
}
return result;
}
};
Python Code：
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
p1 = 0 #首地址
p2 = len(rotateArray)-1 #尾地址
mid = p1 #起初直接将第一个元素作为中间值，如果第一个值小于最后一个值，便直接返回
while rotateArray[p1] >= rotateArray[p2]: #循环条件是，起始的值大于末值
if p2 - p1 == 1: #终止条件是，当起始和末值相邻近
mid = p2 #将末值赋给中间返回
break
mid = (p1 + p2) // 2 #中间值是首末加权平均，python3中//是整除
if rotateArray[mid] == rotateArray[p1] and rotateArray[mid] == rotateArray[p2]:
return self.minInorder(rotateArray) #当三个值全部相等时候，说明有重复的值，采用顺序查找
if rotateArray[mid] >= rotateArray[p1]: #当中间值大于首值时候，说明最小值在后面的数组中
p1 = mid #便将首地址后移
elif rotateArray[mid] <= rotateArray[p2]: #如果中间值小于末值时候，说明最小值在前面的数组中
p2 = mid #便将末值前移
return rotateArray[mid] #其中间值便是最小的值
def minInorder(self,rotateArray): #顺序查找代码
result = rotateArray[0] #假设第一个值是最小值
if len(rotateArray): #特殊测试，测试是否为空
for i in range(len(rotateArray)-1):
if rotateArray[i] > rotateArray[i+1]: #将小于它的值保存起来
result = rotateArray[i+1]
break
return result
总结：
从问题本身入手，明确要处理的问题是什么，要求什么样，时间和空间如何转换。以求最优。