33. 搜索旋转排序数组 (Medium)

专题归类： 09-二分查找 LeetCode 链接： https://leetcode.cn/problems/search-in-rotated-sorted-array/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < len(nums)）上进行了旋转，使数组变为 [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

---

题目详细分析

数据范围含义：

• nums.length <= 5000：O(n) 也能过，但题目要求 O(log n)，必须用二分。
• 所有值互不相同：不需要处理重复值带来的模糊判断（有重复时 nums[mid] == nums[left] 无法判断哪段有序，参见 81-搜索旋转排序数组 II）。

旋转数组的结构：

• 旋转后，数组分成两段有序区间，且两个区间之间有一个”断点”（最小值处）。
• 例如 [4,5,6,7,0,1,2]：左段 [4,5,6,7] 有序，右段 [0,1,2] 有序，且 7 > 0（断点）。
• 任取一个位置 mid，左半段 [left..mid] 和右半段 [mid..right] 至少有一段是完全有序的。

核心洞察：

• 比较 nums[left] 和 nums[mid]：
  • 如果 nums[left] <= nums[mid]：左半段有序。
  • 否则：右半段有序。
• 然后判断 target 是否在有序的那半段里，从而决定搜索方向。

---

小白版直白理解

就像一本字典被人从中间撕开，把后半部分挪到了前面。虽然整体不是完全有序，但”前半部分”和”后半部分”内部仍然是有序的。

比如字典本来是 [A, B, C, D, E, F, G]，被人从 D 处撕开变成了 [E, F, G, A, B, C, D]：

• 前半段 [E, F, G] 还是有顺序的（递增）。
• 后半段 [A, B, C, D] 也是有顺序的（递增）。

查单词时，先看 mid 落在哪个有序段，再判断 target 是否在这个有序段里——在就缩到这段找，不在就去另一段。

---

解题思路

思路一：二分 + 判断有序区间（推荐）

核心思想： 每次二分时，通过比较 nums[left] 和 nums[mid] 确定当前哪一段有序，然后判断 target 是否在有序段内。

算法流程：

1. 计算 mid。
2. 如果 nums[mid] == target，返回 mid。
3. 判断哪段有序：nums[left] <= nums[mid] 则左半有序，否则右半有序。
4. 判断 target 是否在有序段内：
   • 左半有序且 nums[left] <= target < nums[mid]：target 在左半，收缩右边界。
   • 左半有序但 target 不在左半范围：去右半找，收缩左边界。
   • 右半有序同理。

搜索过程可视化（以 nums=[4,5,6,7,0,1,2], target=0 为例）：

初始: left=0, right=6, nums=[4,5,6,7,0,1,2]
第1步: mid=3, nums[3]=7, nums[left]=4 <= 7, 左半[4,5,6,7]有序
       0 < 4(不在左半范围), left=4
第2步: mid=5, nums[5]=1, nums[left]=0 < 1... 不对
       left=4, right=6, mid=5, nums[4]=0, nums[5]=1
       0 <= 1 不成立, 所以右半有序
       nums[5]=1, 右半[0,1,2], target=0 在右半
       left=4, mid=5, nums[4]=0 == target → 返回4

def search(nums, target):
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
 
        if nums[mid] == target:
            return mid
 
        # 判断左半段是否有序
        if nums[left] <= nums[mid]:
            # 左半段有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1  # target 在左半
            else:
                left = mid + 1   # target 在右半
        else:
            # 右半段有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1   # target 在右半
            else:
                right = mid - 1  # target 在左半
 
    return -1

思路二：先找最小值（旋转点），再在有序区间二分

核心思想： 先通过二分找到最小值的位置（即旋转点），然后判断 target 在哪一段有序区间，在该区间内做标准二分。

def search(nums, target):
    # 第一步：找最小值的位置（旋转点）
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    pivot = left  # 最小值的位置
 
    # 第二步：确定 target 在哪个有序区间
    # 在 [pivot, len-1] 或 [0, pivot-1] 中选一个
    if nums[pivot] <= target <= nums[-1]:
        left, right = pivot, len(nums) - 1
    else:
        left, right = 0, pivot - 1
 
    # 第三步：标准二分查找
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return -1

时间复杂度： O(log n) 空间复杂度： O(1)

---

易错点

1. 判断有序段的条件：nums[left] <= nums[mid] 中的等号不能省略。当 left == mid 时（区间缩小到两个元素），等号保证正确判断。
2. target 在有序段内的判断：注意边界——如果 target 在左半有序段，条件是 nums[left] <= target < nums[mid]（右开，排除 mid 自身，因为 mid 已经不等于 target 了）。
3. 区间收缩方向：初学者容易把 left/right 的更新方向搞反。记住：“target 在一段，就缩到这一段；不在，就去另一段。”
4. 重复元素问题：如果数组有重复元素（81 题），nums[left] == nums[mid] 时无法判断哪段有序，需要 left += 1 跳过。
5. pivot 思路中的边界：当 pivot == 0 时（数组实际上没有旋转），nums[pivot] <= target <= nums[-1] 覆盖了整个数组。

---

框架提炼

旋转数组二分模板：

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
 
        if nums[mid] == target:
            return mid
 
        if nums[left] <= nums[mid]:          # 左半有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1              # target 在左半
            else:
                left = mid + 1               # target 在右半
        else:                                 # 右半有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1               # target 在右半
            else:
                right = mid - 1              # target 在左半
 
    return -1

核心思维： “二分查找的精髓不是找到有序数组，而是在每次迭代中，排除一半不可能的区域。“即使整体无序，只要能确定一半是有序的，就能做出排除决策。

其他旋转数组问题对比：

问题	目标	比较对象
33-搜索旋转排序数组	找 target	比较 nums[left] 和 nums[mid]
153-寻找最小值	找最小值	比较 nums[mid] 和 nums[right]

---

关联题目

• 153-寻找旋转排序数组中的最小值 — 更简单的旋转数组问题，只需找到最小值，与本题区分比较对象（mid vs right）。
• 35-搜索插入位置 — 标准有序数组二分，旋转数组二分的基础，建议先掌握。
• 81-搜索旋转排序数组II — 包含重复元素的版本，当 nums[left] == nums[mid] 时需要 left++ 跳过。
• 74-搜索二维矩阵 — 将矩阵展开为一维有序数组的二分，与本题的”部分有序”思想不同但同为二分变体。