33. Search in Rotated Sorted Array

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

题目要求我们从一个升序排序后的数组 nums 中找出 target 的下标

有趣的是，nums 在排序后会被往左旋转任意次

举个例子：[0,1,2,4,5,6,7] 往左旋转 3 次会变成 [4,5,6,7,0,1,2]

解题思路

这题题目要求我们用 logn 的复杂度来解，所以我们优先考虑使用二分搜索来解

由于题目加了旋转的限制，所以我们需要对二分搜索进行部份改造：

1. 二分搜索的结构还是一样的，我们先计算出中间元素的下标 mid

2. 接下来我们需要判断 mid 的哪一边是正常的升序：

   • 如果 nums[mid] >= nums[left] 代表 mid 的左边是升序排列
   • 如果 nums[mid] <= nums[right] 代表 mid 的右边是升序排列

3. 如果 mid 的左边是升序，那么我们可以通过判断 target 在不在左边来修改二分搜索的范围；反之亦然

Javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0
    let right = nums.length - 1

    while(left <= right) {
        let mid = (left + right) >> 1

        if(nums[mid] === target) {
            return mid
        }

        if(nums[left] <= nums[mid]) {
            // the left half is sorted
            if(target <= nums[mid] && target >= nums[left]) {
                // if the target is in left half
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // the right half is sorted
            if(target <= nums[right] && target >= nums[mid]) {
                // if the target is in right half
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
};