二分查找
解题思路
定义两个指针 left、right 分别位于数组的两端；
当 mid 在 1 位置的时候
mid > right，说明一定被反转了（因为没有被反转的数组是单调递增的），则最小值在 mid 右侧，为了找到最小值，左边的指针向右移动一位left = mid+1；当 mid 在 2 位置的时候
mid < right，说明 mid 到 right 之间是递增的，最小值有可能在 mid 的左边，或者 mid 就是最小值，则right = mid；
复杂度
-
时间复杂度：时间复杂度为
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🧑💻 349. 两个数组的交集
上一篇
评论
