好的，我们这次来详细讲解 LeetCode 第 33 题：搜索旋转排序数组（Search in Rotated Sorted Array）。

1. 题目描述

题意：
一个原本按升序排列的整数数组 nums，在某个未知的下标 k（0 <= k < nums.length）处进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。

例如：[0,1,2,4,5,6,7] 在下标 3 处旋转 → [4,5,6,7,0,1,2]。

给你一个目标值 target，如果 nums 中存在这个目标值，则返回它的下标，否则返回 -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

2. 题目理解与思路分析

2.1 数组特点

旋转排序数组的特点是：

• 被分成了两个有序部分（左半段和右半段），每个部分内部是升序的。
• 左半段的所有元素 ≥ 右半段的所有元素（因为原数组严格升序，旋转只是把前面一段搬到后面）。

例如：[4,5,6,7,0,1,2]

• 左半段：[4,5,6,7]（≥ 右半段所有值）
• 右半段：[0,1,2]

2.2 要求 O(log n) 时间

O(log n) 提示我们要用二分查找。

但数组不是全局有序的，直接对整个数组二分会出错，因为 mid 可能落在左半段或右半段，并且 target 可能位于任意一半。

3. 核心思路：二分查找的改造

3.1 如何判断哪部分有序

选取中点 mid = (left + right) // 2，比较 nums[mid] 与 nums[left] 或 nums[right] 可判断 mid 落在哪一半。

常用方法：比较 nums[mid] 与 nums[left]：

• 如果 nums[mid] >= nums[left]，说明 mid 在左半段（因为左半段整体 ≥ 右半段第一个元素）。
• 否则，mid 在右半段。

3.2 判断 target 在哪一半

知道 mid 在左半段还是右半段后，就可以判断 target 是否在有序的那一半中：

• 如果 mid 在左半段（即 nums[left] <= nums[mid]）：

  • 左半段有序范围是 [left, mid]。
  • 如果 target 在 [nums[left], nums[mid]] 之间，则 target 在左半段，应让 right = mid - 1。
  • 否则 target 在右半段，left = mid + 1。

• 如果 mid 在右半段（即 nums[left] > nums[mid]）：

  • 右半段有序范围是 [mid, right]。
  • 如果 target 在 [nums[mid], nums[right]] 之间，则 target 在右半段，应让 left = mid + 1。
  • 否则 target 在左半段，right = mid - 1。

4. 详细步骤演示

以 nums = [4,5,6,7,0,1,2], target = 0 为例：

初始：left = 0, right = 6

Step 1：

• mid = 3，nums[3] = 7，nums[left] = 4 → 7 >= 4 → mid 在左半段。
• 左半段 [4,5,6,7] 有序。
• target = 0 不在 [4, 7] 之间 → 去右半段找：left = mid + 1 = 4。

Step 2：left = 4, right = 6

• mid = 5，nums[5] = 1，nums[left] = 0 → 1 >= 0？ 这里注意：现在 left=4，nums[left]=0，nums[mid]=1，1 >= 0 成立，所以 mid 在左半段？ 等等，这里要小心，我们应统一用 nums[left] 与 nums[mid] 比较来判断左右半段，但此时整个区间 [4,6] 其实是右半段整体，所以 nums[left]=0，nums[mid]=1 都小于 nums[0]=4，所以它们都在右半段。
  更稳妥的方法：比较 nums[mid] 与 nums[left] 时，left 是当前区间左边界，但“左半段”“右半段”是相对于整个数组的旋转点来说的，其实我们只需判断：nums[mid] >= nums[left] 说明 [left, mid] 有序；否则 [mid, right] 有序。
  这里 nums[5]=1，nums[4]=0 → 1 >= 0 成立，所以 [4,5] 有序（确实，[0,1] 升序）。
• 有序区间 [4,5] 的值范围 [0,1]，target=0 在 [0,1] 之间吗？是的，在 [nums[left]=0, nums[mid]=1] 之间。
• 所以应向左半部分找：right = mid - 1 = 4。

Step 3：left = 4, right = 4

• mid = 4，nums[4] = 0，等于 target，返回 4。

5. 边界情况与代码实现

注意当 left == right 时的处理，以及当 nums[mid] == target 时直接返回。

def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        
        # 判断 [left, mid] 是否有序
        if nums[left] <= nums[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
    return -1

6. 复杂度分析

• 时间复杂度：O(log n)，每次将搜索区间减半。
• 空间复杂度：O(1)，只用了几个变量。

7. 关键点总结

1. 旋转排序数组二分时，先通过 nums[left] 与 nums[mid] 比较判断哪一半有序。
2. 判断 target 是否在有序的那一半区间内，从而决定搜索方向。
3. 等于 target 时提前返回。
4. 处理边界如 left == right 和空输入。

这样，即使数组被旋转，我们也能在 O(log n) 时间内找到目标值。