思路:
- 初始化 :初始化start和end分别指向nums数组的左右两端
- 循环二分:令mid = (start + end) / 2(start <= mid < end),分以下三种情况:
(1)当nums[mid] >nums[j]时,则选转点在左排序数组中,即在[mid + 1, j]中,此时令i = mid + 1;
(2)当nums[mid] < nums[j]时,则旋转点在[i, mid]中,则令j = mid;
(3)当nums[mid] = nums[j]时,无法判断,解决:令j = j - 1;- 返回值:当i = j 时跳出二分循环,并返回旋转点的值nums[i]即可。
class Solution {
public:
int minArray(vector<int>& numbers) {
int i = 0, j = numbers.size() - 1;
while (i < j) {
int m = (i + j) / 2;
if (numbers[m] > numbers[j]) i = m + 1;
else if (numbers[m] < numbers[j]) j = m;
else j--;
}
return numbers[i];
}
};