二分查找
解题思路
定义两个指针 left、right 分别位于数组的两端；
当 mid 在 1 位置的时候如果
mid > right，说明一定被反转了（因为没有被反转的数组是单调递增的），则最小值在 mid 右侧，为了找到最小值，左边的指针向右移动一位left = mid+1，此时右侧是非递减的序列，可以用常规的二分处理；当 mid 在 2 位置的时候
mid < right，说明 mid 到 right 之间是递增的，最小值有可能在 mid 的左边，或者 mid 就是最小值，则right = mid，此时右侧是非递减的序列，可以用常规的二分处理；当 mid 在 3 位置的时候
mid === right，要缩减右侧范围，但是不知道有几个与 mid 相同的值，没有关系，right - 1 缩减一个长度，如果下一次是 mid === right 则继续 right - 1 ， 直到序列变成 153 的样子；
复杂度
-
时间复杂度：时间复杂度为
O(logn)，其中 n 是数组 nums 的长度 -
空间复杂度：
O(1)
代码实现
var findMin = function (nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
// 向下取整
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1; // 此时节点位于图解 1 的位置
} else {
right = mid; // 此时节点位于图解 2 的位置
}
}
return nums[left]; // 跳出 while 循环后 left 和 right 是相等的
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 153. 寻找旋转排序数组中的最小值
上一篇
评论
