Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

33. 搜索旋转排序数组 #17

Open
webVueBlog opened this issue Sep 3, 2022 · 0 comments
Open

33. 搜索旋转排序数组 #17

webVueBlog opened this issue Sep 3, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

33. 搜索旋转排序数组

Description

Difficulty: 中等

Related Topics: 数组, 二分查找

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

在传递给函数之前,nums 在预先未知的某个下标 k0 <= 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

提示:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 * 二分搜索
 * 关键字:排序,搜索
 */
var search = function(nums, target) {
    let [left, right] = [0, nums.length - 1]

    while (left <= right) {
        const mid = (left + right) >>> 1
        if (nums[mid] === target) return mid

        if (nums[mid] > nums[right]) {
            if (nums[left] <= target && nums[mid] > target) right = mid - 1
            else left = mid + 1
        } else {
            if (nums[mid] < target && nums[right] >= target) left = mid + 1
            else right = right - 1
        }
    }
    return -1
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant