class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { // 整体思路:二分法确定拐点位置 int len = rotateArray.size(); int left = 0, right = len - 1; // 特殊情况:开头元素小于末尾元素,直接返回第一个值 if (rotateArray[left] < rotateArray[right]) { return rotateArray[left]; } while (left < right) { int mid = (right + left) / 2; // 前两种是找到了拐点 if (rotateArray[mid] > rotateArray[mid + 1]) { return rotateArray[mid + 1]; } else if (rotateArray[mid] < rotateArray[mid - 1]) { return rotateArray[mid]; } else if (rotateArray[mid] > rotateArray[right]) { // 当前中间点大于最右边元素,说明左边可以削 left = mid + 1; } else { // 左边不行,就削右边 right = mid; } } return 0; } };