33.搜索旋转索引数组(javascript)33.SearchinRotatedSortedArray

整数数组 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) 该算法解决了这个问题。

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

示例 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

var search = function (nums, target) {
    // 二分查找
    // 初始化左右指针
    var l = 0
    var r = nums.length - 1
    while (l <= r) {
        // 取中值
        var mid = Math.floor((l + r) / 2)
        // 遇到的目标值返回下标
        if (nums[mid] === target) {
            return mid
        }
        // 当nums[l] <= nums[mid]时，l到mid升序,否则mid到r升序
        if (nums[l] <= nums[mid]) {
            //当目标值存在于nums[l] 到 nums[mid] 范围内,r指针向左移动，否则l指针右移
            if (nums[l] <= target && target < nums[mid]) {
                r = mid - 1
            } else {
                l = mid + 1
            }
        } else {
            //当目标值存在于nums[mid] 到 nums[r] 范围内,l指针向右移动，否则r指针左移
            if (nums[mid] < target && target <= nums[r]) {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
    }
    return -1
};

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