0033. 搜索旋转排序数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 二分查找

1. 📝 题目描述

• leetcode

整数数组 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) 的算法解决此问题。

---

示例 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
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

2. 🎯 s.1 - 二分查找

c

int search(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;

        // 左半有序
        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;
            }
        }
    }

    return -1;
}

js

/**
 * @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) >> 1
    if (nums[mid] === target) return mid

    // 左半有序
    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
      }
    }
  }

  return -1
}

py

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

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

            # 左半有序
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # 右半有序
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

• 时间复杂度：$O(\log n)$，每次二分排除半个搜索序列
• 空间复杂度：$O(1)$，只使用了常数级别的额外变量

算法思路：

• 旋转排序数组将一个升序数组分成两段，对于任意中间点 mid，左半 [left, mid] 和右半 [mid, right] 中必有一半是有序的
• 判断左半是否有序：nums[left] <= nums[mid]
  • 成立 => 左半有序：若 target 在 [nums[left], nums[mid]) 内，就在左半，否则去右半
  • 不成立 => 右半有序：若 target 在 (nums[mid], nums[right]] 内，就在右半，否则去左半
• 循环结束未命中则返回 -1