如何在旋转过的有序数组中搜索目标值？

直接回答：二分查找，但每轮先判断哪一半是有序的。旋转数组从中点切开后，[lo, mid] 和 [mid, hi] 至少有一侧保持有序：若 nums[lo] <= nums[mid] 则左半有序，此时目标在左半的条件是 nums[lo] <= target < nums[mid]，否则去右半；反之右半有序，对称处理。每轮排除一半，时间 O(log n)、空间 O(1)。

展开解析：关键是把「单调性全局成立」换成「单调性局部成立」：虽然整体不单调，但切开后必有一侧单调，于是可以在有序侧做精确的范围判断，在另一侧递归处理。边界细节是常见的扣分点：判断左半有序用 <=（应对 lo == mid 的两元素情形）、收缩边界 lo = mid + 1 / hi = mid − 1 防死循环。经典变体：含重复元素的旋转数组（nums[lo] == nums[mid] 时无法判断哪侧有序，只能 lo += 1 线性收缩，最坏退化 O(n)）、找旋转数组的最小值（与右端点比较的二分）、旋转点下标即最小值下标（等价转化）。追问方向：为什么与右端点比较找最小值更稳妥、二分模板「循环不变量」的陈述。

示例：

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