搜索旋转排序数组

题目描述

整数数组 nums 按升序排列，数组中的值 互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 ⇐ k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。

给你 旋转后 的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1： 输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2： 输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3： 输入：nums = [1], target = 0
输出：-1

思路&js代码

1、两次二分查找

// 153. 寻找旋转排序数组中的最小值（返回的是下标）
var findMin = function(nums) {
    let left = -1, right = nums.length - 1; // 开区间 (-1, n-1)
    while (left + 1 < right) { // 开区间不为空
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] < nums[nums.length - 1]) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
};
 
// 有序数组中找 target 的下标
var lowerBound = function(nums, left, right, target) {
    while (left + 1 < right) { // 开区间不为空
        // 循环不变量：
        // nums[right] >= target
        // nums[left] < target
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            right = mid; // 范围缩小到 (left, mid)
        } else {
            left = mid; // 范围缩小到 (mid, right)
        }
    }
    return nums[right] === target ? right : -1;
};
 
var search = function(nums, target) {
    const i = findMin(nums);
    if (target > nums[nums.length - 1]) { // target 在第一段
        return lowerBound(nums, -1, i, target); // 开区间 (-1, i)
    }
    // target 在第二段
    return lowerBound(nums, i - 1, nums.length, target); // 开区间 (i-1, n)
};

2、一次二分查找

var search = function(nums, target) {
    const end = nums[nums.length - 1];
    function check(i) {
        const x = nums[i];
        if (x > end) {
            return target > end && x >= target;
        }
        return target > end || x >= target;
    }
 
    let left = -1, right = nums.length - 1; // 开区间 (-1, n-1)
    while (left + 1 < right) { // 开区间不为空
        const mid = Math.floor((left + right) / 2);
        if (check(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return nums[right] === target ? right : -1;
};