一 题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
二 解法一
1 分析
遍历数组，找出数组中的最小元素。这个方法很直接，但是不是最好的，因为题目描述中还给了一些条件没有用到，比如说非递减排序。
时间复杂度O(n)，空间复杂度O(1)。
2 代码实现略。
三 解法二
1 分析
非递减数组其实也就是有序数组，既然是有序数组那么就可以考虑用二分法。
2 代码实现
1 class Solution { 2 public: 3 int minNumberInRotateArray(vector<int> rotateArray) { 4 int size = rotateArray.size(); 5 if (size == 0) return 0; 6 7 int low = 0, high = size - 1; 8 int mid; 9 while (low < high) 10 { 11 mid = low + ((high - low) >> 1); 12 if (rotateArray[mid] > rotateArray[high]) 13 low = mid + 1; 14 else if (rotateArray[mid] < rotateArray[high]) 15 high = mid; 16 else 17 high -= 1; 18 } 19 20 return rotateArray[low]; 21 } 22 };
最好情况时间复杂度O(logn)，最坏情况时间复杂度O(n)；空间复杂度O(1)。
该篇博客为自己的学习总结，水平有限，如有错误，欢迎交流！