题目描述 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路
转自 https://blog.csdn.net/htt789/article/details/80970533
输入的数组为非减排序数组的旋转，数组分为两个排好序的数组。{3,4,5,1,2}其中前半部分{3,4,5}和后半部分{1,2}都为非减数组，且前半部分的数大于等于后半部分。
对于排序的数组->二分查找
1.取数组中间数，若中间的数大于数组第一个数，说明中间数位于前半个非递减数组中，因此最小值在数组的后半部分，3 4 5 6 0 1 2。
2.若中间数小于数组最后一个数，说明中间数位于后半个非递减数组中，因此最小值在数组的前半部分, 4 5 1 2 3。
3.若数组起始数，中间数，末位数相同，则不能判断最小值位于数组的前半部分还是后半部分，需要采用暴力排序，依次比较查找。（特殊输入：重复数字的数组） 1 1 1 0 1
4.直到指向数组前和后的指针下标相邻时，后面的指针对应数组的最小数字。
测试用例：
- 边界值测试：输入直接为非递减数组（未经过旋转），如果第一个数字小于最后一个数字，说明数组递增，可以直接返回第一个数字作为最小数字。
- 输入数组含有重复的数字
代码
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.empty()) return 0;
int left = 0, right = rotateArray.size() - 1;
while (left < right) {
//确认子数组是否是类似1,1,2,4,5,..,7的非递减数组
if (rotateArray[left] < rotateArray[right]) return rotateArray[left];
int mid = left + (right - left) / 2;
//如果左半数组为有序数组
if (rotateArray[left] < rotateArray[mid])
left = mid + 1;
//如果右半数组为有序数组
else if (rotateArray[mid] < rotateArray[right])
right = mid;
//否则，rotateArray[left] == rotateArray[mid] == rotateArray[right]
else {
++left;
}
}
return rotateArray[left];
}
};