0033-search-in-rotated-sorted-array.md

33. 搜索旋转排序数组

项目	内容
链接	LeetCode CN
标签	二分 · 数组
源码	0033-search-in-rotated-sorted-array.py

---

一、题目理解

题意

升序数组在某个点旋转后（无重复），判断 target 是否存在并返回下标。

示例

原数组 [0,1,2,4,5,6,7]
旋转 @4 → [4,5,6,7,0,1,2]
target=0 → 返回 4
target=3 → 返回 -1

旋转数组结构

[4, 5, 6, 7 | 0, 1, 2]
 ← 左半有序 → ← 右半有序 →
       ↑ pivot

任意 mid 必落在某一有序半段内，可判断 target 是否在有序半段。

flowchart TD
    M[mid] --> L{nums[left] <= nums[mid]?}
    L -->|左半有序| T1{target 在 left..mid?}
    L -->|右半有序| T2{target 在 mid..right?}
    T1 -->|是| R1[right=mid-1]
    T1 -->|否| L1[left=mid+1]
    T2 -->|是| L2[left=mid+1]
    T2 -->|否| R2[right=mid-1]

Loading

---

二、思路总览

方法	说明
递归 DFS	边界条件多，易错
迭代二分（推荐）	判断哪半有序，决定搜哪边

---

三、解法演进

方法一：递归 DFS

按 nums[i] 与 target 关系决定搜左或右，需处理 i+1==j 等边界。。

---

方法二：迭代二分（推荐）

思路：

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

走查 [4,5,6,7,0,1,2], target=0：

left	right	mid	nums[mid]	有序半	决策
0	6	3	7	左半 4..7	0 不在 → left=4
4	6	5	1	右半 0,1,2	0 在 → right=4
4	4	4	0	找到	return 4

---

四、实现代码

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            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)

注意：

• nums[left] <= nums[mid] 用 <=：当 left==mid 时仍成立
• 判断 target 区间时用 <= / < 要与题意一致
• 有重复元素需另题（LeetCode 81）