旋转数组中的最小数字
C++。二分。。。left表示当前查找范围的左边界，right表示当前查找范围的右边界，mid = (left + right) / 2;。
分以下情况：
- 如果
rotateArray[mid] >= rotateArray[left]，说明那个旋转点在mid的右边，则有：left = mid;
- 如果
rotateArray[mid] <= rotateArray[right]，说明那个旋转点在mid的左边边，则有：right = mid;
- 如果
left == right - 1，说明已经到了旋转点了，此时left在最大值点，right在最小值点。
特殊情况：
- 如果出现
1 0 1 1 1这种序列，会出现rotateArray[left] == rotateArray[mid] && rotateArray[mid] == rotateArray[right]的情况，此时二分法就失效了，直接在[left, right]范围里顺序查找； - 如果序列中所有元素都相等，也是如同特殊情况1，只能顺序查找，毕竟之前没法确定是不是全部都是相等的。
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int left = 0, right = rotateArray.size() - 1;
while (rotateArray[left] >= rotateArray[right]) {
int mid = (left + right) / 2;
if (left == right - 1) return rotateArray[right];
if (rotateArray[left] == rotateArray[mid] && rotateArray[mid] == rotateArray[right])
return order_find(rotateArray, left, right);
if (rotateArray[mid] >= rotateArray[left])
left = mid;
else if(rotateArray[mid] <= rotateArray[right])
right = mid;
}
return rotateArray[left];
}
int order_find(vector<int> &rotateArray, int left, int right) {
int ans = rotateArray[left];
for (int i = left + 1; i <= right; i++)
ans = min(ans, rotateArray[i]);
return ans;
}
};
