Skip to main content

搜索旋转排序数组

2022/07/17

https://leetcode.cn/problems/search-in-rotated-sorted-array/

示例​

示例一​

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

示例二​

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

示例三​

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

题解参考​

双指针​

根据题目描述，可以确定该数组以k位置分割，左右两边的排序是升序；那么可以利用这个k作为中间点，在left与k之间，right与k之间，寻找target；

var search = function (nums, target) {
    const n = nums.length
    if (n === 0) {
        return -1
    }
    if (n === 1) {
        return nums[0] === target ? 0 : -1
    }
    let left = 0
    let right = n - 1
    while (left <= right) {
        const mid = Math.floor((left + right) / 2)
        if (nums[mid] === target) {
            return mid
        }
        if (nums[0] <= nums[mid]) {
            if (nums[0] <= target && target < nums[mid]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if (nums[mid] < target && target <= nums[n - 1]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
};