二分查找,数组要么没有旋转,要么旋转成为两段局部有序的子数组。如果mid的值大于right端点的值,说明只可能是两段有序的子数组,且最小值必定出现在mid右端;如果小于,说明两种情况都可能存在,但此时最小值必定出现在mid左端;如果等于,无法判断最小值出现的区间,但是可以肯定right不会是唯一最小值(即使是最小值也有mid的值与它相同,减去没有影响),所以可以把right减一。
class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int l = 0, r = rotateArray.size() - 1; while (l < r) { // cout << l << " " << r << endl; int mid = l + (r - l) / 2; if (rotateArray[mid] < rotateArray[r]) r = mid; else if (rotateArray[mid] > rotateArray[r]) l = mid + 1; else r--; } return rotateArray[l]; } };