好的，我们这次来详细讲解 LeetCode 第 33 题「搜索旋转排序数组」。

这是一道非常经典的二分查找变形题，能够很好地锻炼你对二分查找思想的理解和灵活应用能力。

第一步：题目描述

题目

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

在传递给函数之前，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]。

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

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例

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

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

输入：nums = [1], target = 0
输出：-1

第二步：理解问题本质与核心挑战

1. 有序但被“切断”了：数组原本是完全有序的，但旋转操作将其分成了两个有序的部分。前半段的所有元素都大于后半段的所有元素（因为原数组升序且无重复）。
2. 核心挑战：虽然数组整体不是有序的，但它是由两个有序片段拼接而成，并且我们仍然可以找到一种规律，利用 二分查找 在 O(log n) 的时间内解决问题。
3. 关键观察：当我们取数组的中间点 mid 时，这个中间点一定位于至少一个有序片段之内（可能是左半段有序片段，也可能是右半段有序片段）。我们可以通过比较 nums[mid] 和 nums[left]（或 nums[right]）来判断 mid 位于哪个有序片段。

第三步：思路推导（循序渐进）

让我们用一个例子来推演：nums = [4, 5, 6, 7, 0, 1, 2], target = 0。

传统二分查找的核心是每次通过比较 target 和 nums[mid]，可以确定地抛弃掉一半的搜索空间。在这里，由于数组不是全局有序，我们不能直接这么做。但我们可以退一步：

我们的目标是：每次二分后，都能确定 target 位于哪一半（左半部分 [left, mid] 或右半部分 [mid+1, right]）。

如何实现这个目标？答案是：先判断 mid 落在哪个有序片段里，然后判断 target 是否在那个有序片段中。

详细步骤分解

1. 计算中间索引：mid = (left + right) / 2。

2. 情况一：nums[mid] 位于左半段有序片段（即 nums[left] <= nums[mid]）

   • 解释：如果中间值大于等于最左值，说明从 left 到 mid 这一段是严格升序的，没有受到旋转点的影响。
   • 判断逻辑：
     • 如果 target 也在这个有序片段内，即 nums[left] <= target < nums[mid]，那么我们可以安全地将搜索范围缩小到左半部分：right = mid - 1。
     • 否则（target 不在此有序片段内），它肯定在右半部分（包括 mid 的另一侧）：left = mid + 1。

3. 情况二：nums[mid] 位于右半段有序片段（即 nums[left] > nums[mid]）

   • 解释：如果中间值小于最左值，说明旋转点就在 left 和 mid 之间，那么从 mid 到 right 这一段是严格升序的。
   • 判断逻辑：
     • 如果 target 也在这个有序片段内，即 nums[mid] < target <= nums[right]，那么我们可以安全地将搜索范围缩小到右半部分：left = mid + 1。
     • 否则（target 不在此有序片段内），它肯定在左半部分：right = mid - 1。

简单总结决策逻辑：

每次二分，先根据 nums[mid] 和 nums[left] 的关系，判断哪一半是完全有序的。然后检查 target 是否在这个有序的一半里，如果是，就在这一半里找；如果不是，就一定在另一半里找。

第四步：完整代码实现（带详细注释）

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 如果数组为空，直接返回-1
        if not nums:
            return -1
        
        # 初始化左右指针
        left, right = 0, len(nums) - 1
        
        # 开始二分查找循环
        while left <= right:
            # 计算中间索引，防止大数溢出
            mid = (left + right) // 2
            
            # 情况1：幸运地直接找到了目标值
            if nums[mid] == target:
                return mid
            
            # 情况2：中间点位于左半段有序序列（例如 [4,5,6,7]）
            if nums[left] <= nums[mid]:
                # 判断target是否在这个有序的左半段内
                if nums[left] <= target < nums[mid]:
                    # 如果在，则抛弃右半部分，在左半部分继续搜索
                    right = mid - 1
                else:
                    # 如果不在，则说明target在右半部分（可能无序）
                    left = mid + 1
            # 情况3：中间点位于右半段有序序列（例如 [0,1,2]）
            else:
                # 判断target是否在这个有序的右半段内
                if nums[mid] < target <= nums[right]:
                    # 如果在，则抛弃左半部分，在右半部分继续搜索
                    left = mid + 1
                else:
                    # 如果不在，则说明target在左半部分
                    right = mid - 1
        
        # 循环结束仍未找到，返回-1
        return -1

第五步：用示例进行推演

我们以 nums = [4, 5, 6, 7, 0, 1, 2], target = 0 来走一遍流程。

1. 初始状态: left = 0, right = 6。

   • mid = (0+6)//2 = 3。nums[mid] = 7。
   • 判断 nums[left] (4) <= nums[mid] (7)？是，所以 mid 在左半段有序序列 [4,5,6,7]。
   • target (0) 是否在 [4, 7) 区间内？否。
   • 所以，抛弃左半部分，left = mid + 1 = 4。

2. 第二轮: left = 4, right = 6。

   • mid = (4+6)//2 = 5。nums[mid] = 1。
   • 判断 nums[left] (0) <= nums[mid] (1)？是，所以 mid 在（新的）左半段有序序列 [0,1,2]。
   • target (0) 是否在 [0, 1) 区间内？是。
   • 所以，抛弃右半部分，right = mid - 1 = 4。

3. 第三轮: left = 4, right = 4。

   • mid = (4+4)//2 = 4。nums[mid] = 0。
   • nums[mid] == target？是！
   • 返回 mid = 4。

结果正确。

第六步：复杂度分析与总结

• 时间复杂度：O(log n)。每次迭代都将搜索范围缩小一半，与标准二分查找相同。
• 空间复杂度：O(1)。只使用了常数级别的额外空间。

核心思想总结：
这道题的精髓在于，它打破了我们对二分查找必须应用于全局有序数组的刻板印象。它教会我们，二分查找的本质是 “每次排除一半不可能的区域”。只要我们能通过某种方法（在这里是通过判断哪一半是有序的）来 reliably（可靠地）排除一半数据，就可以使用二分查找。

希望这个从问题理解到思路推导，再到代码实现和实例推演的完整过程，能帮助你彻底掌握这道经典的题目！