153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
153. 寻找旋转排序数组中的最小值 - 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2],...
思路
变形的二分还是二分。这次二分的目标是找到单调性改变的那个位置。
另外这翻译还是有点别扭。不如直接说“输入数组是某个长度为n的升序数组旋转[1..n]次的结果”。
代码
class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] < nums[r]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}
}
1 个帖子 - 1 位参与者
来源: LinuxDo 最新话题查看原文