搜索旋转排序数组

题目

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

在传递给函数之前, nums 在预先未知的某个下标 k(0 <= k < nums.length) 上进行了旋转, 例如, [0, 1, 2, 4, 5, 6, 7] 在下标 3 处经旋转后可能变为 [4, 5, 6, 7, 0, 1, 2].

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

提示:

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

示例

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

输出: 0

题解

可以发现的是, 我们将数组从中间分开成左右两部分的时候, 一定有一部分的数组是有序的. 拿示例来看, 我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分, 其中左边 [4, 5, 6] 这个部分的数组是有序的.

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [left, mid) 和 [mid + 1, right] 哪个部分是有序的, 并根据有序的那个部分确定该如何改变二分查找的上下界, 因为我们能够根据有序的那部分判断出 target 在不在这个部分:

• 如果 [left, mid - 1] 是有序数组, 且 target 的大小满足 [nums[left], nums[mid]], 则我们应该将搜索范围缩小至 [left, mid - 1], 否则在 [mid + 1, right] 中寻找.
• 如果 [mid, right] 是有序数组, 且 target 的大小满足 [nums[mid], nums[right]], 则我们应该将搜索范围缩小至 [mid + 1, right], 否则在 [left, mid - 1] 中寻找.

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) {
    const mid = (left + (right - left) / 2) | 0
    if (nums[mid] === target) return mid

    // nums[left] <= nums[mid] 即可判断左边那片是有序的
    if (nums[left] <= nums[mid]) {
      // 如果 target 落在左边这片, 那搜索范围就缩小成 [left, mid - 1]
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1
      } else {
        // 否则搜索范围就缩小成 [mid + 1, right]
        left = mid + 1
      }
      // 如果右边是有序的
    } else {
      // 如果 target 落在右边这片, 那搜索范围就缩小成 [mid + 1, right]
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1
      } else {
        // 否则搜索范围就缩小成 [left, mid - 1]
        right = mid - 1
      }
    }
  }

  return -1
}

Rust

pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let (mut left, mut right) = (0, nums.len() - 1);

    while left <= right {
        let mid = (left + right) / 2;

        if nums[mid] == target {
            return mid as i32;
        }

        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    -1
}

复杂度分析

时间复杂度: O(logn)

空间复杂度: O(1), 只需要常数级别的空间存放变量.