0Pricing
DSA Interview Prep · 课时

旋转数组与无序数组中的二分查找

通过在每一步判断哪一半有序，解决旋转有序数组查找和旋转数组求最小值问题。

旋转数组与无序数组中的二分查找 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

什么是旋转有序数组

旋转有序数组是指在某个枢轴位置切开一个有序数组，然后交换两部分所得的数组。例如，[4, 5, 6, 7, 0, 1, 2] 是有序数组 [0,1,2,4,5,6,7] 在索引 4 处旋转后的结果。标准二分查找在这里会失效，因为数组不再是全局有序的。

关键洞察是：经过任意旋转后，数组中至少有一半始终保持有序。在决定如何移动边界之前，您的二分查找必须先确定哪一半是有序的。

# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossing

识别有序的半部分

计算出 mid 后，将 arr[lo] 与 arr[mid] 进行比较。如果 arr[lo] <= arr[mid]，则左半部分已排序；否则右半部分已排序。确定哪一半已排序后，您就可以检查目标值是否位于该有序范围内，并据此缩小搜索范围。

这种决策树使您每一步都能恰好排除数组的一半，即使数组发生旋转，也能保持 O(log n) 的复杂度。

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1

逐步演示一个示例

让我们逐步跟踪 search_rotated([4,5,6,7,0,1,2], 0) 的执行过程。初始时 lo=0, hi=6, mid=3, arr[mid]=7。目标值 0 位于有序的左半部分 [4..7] 中吗？不在，因此将 lo=4。现在 lo=4, hi=6, mid=5, arr[mid]=1。左半部分 [0,1] 已排序（arr[lo]=0 <= arr[mid]=1）。0 位于 [0..1) 中吗？是，因此将 hi=4。现在 lo=4, hi=4, mid=4, arr[4]=0——在索引 4 处找到目标值。

# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
    if nums[mid] == target:
        steps.append(f'Found at {mid}')
        break
    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
for s in steps:
    print(s)

处理旋转数组中的重复值

当旋转后的数组可能包含重复值（例如 [1,3,1,1,1]）时，条件 nums[lo] == nums[mid] 存在歧义——您无法判断哪一半已排序。稳妥的处理方式是将 lo 加 1（或将 hi 减 1）后重试。这样最坏情况下的时间复杂度会退化为 O(n)，您应当向面试官说明这一点。

def search_rotated_with_dups(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return True
        # Ambiguous: shrink left boundary
        if nums[lo] == nums[mid] == nums[hi]:
            lo += 1
            hi -= 1
        elif 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 False

print(search_rotated_with_dups([1, 3, 1, 1, 1], 3))  # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0))  # True

查找旋转后有序数组中的最小值

还有一种相关问题：在不针对特定目标值进行搜索的情况下，查找旋转后有序数组中的最小元素。最小值始终位于无序的一半中。每一步中：如果 arr[mid] > arr[hi]，最小值位于右半部分（lo = mid + 1）；否则最小值位于包括 mid 在内的左半部分（hi = mid）。当 lo == hi 时，您就找到了最小值。

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1   # min is in right half
        else:
            hi = mid       # min is at mid or left of mid
    return nums[lo]

print(find_min([3, 4, 5, 1, 2]))   # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0
print(find_min([11, 13, 15, 17]))  # 11 (no rotation)

为什么 arr[lo] <= arr[mid] 能识别出有序的左半部分

条件 arr[lo] <= arr[mid] 有效，是因为在一个有序（或未发生旋转的有序）片段中，第一个元素始终是最小的。如果 arr[lo] <= arr[mid]，说明 [lo..mid] 内没有发生旋转，因此这一半是有序的。等号用于处理 lo == mid 的情况，因为单元素片段自然是有序的。

相反，如果 arr[lo] > arr[mid]，旋转枢轴一定位于 lo 和 mid 之间，这意味着右半部分 [mid..hi] 是连续的有序片段。

# Visualise: detect which half is sorted
examples = [
    ([4, 5, 6, 7, 0, 1, 2], 0, 6),  # mid=3, val=7 => left sorted
    ([6, 7, 0, 1, 2, 4, 5], 0, 6),  # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
    mid = lo + (hi - lo) // 2
    if arr[lo] <= arr[mid]:
        print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]}  => LEFT half sorted')
    else:
        print(f'arr[{lo}]={arr[lo]} >  arr[{mid}]={arr[mid]}  => RIGHT half sorted')

复杂度分析

使用二分查找搜索旋转后的有序数组，时间复杂度仍为 O(log n)，空间复杂度仍为 O(1)，因为我们在每次迭代中仍将搜索空间缩小一半。与经典二分查找的唯一差别，是增加了一次常数时间的检查，用于识别哪一半已排序。

存在重复值时，最坏情况会退化为 O(n)，因为我们每一步可能只能将 lo 增加 1。请明确说明这一权衡——这表明您会考虑常规路径之外的边界情况。

LeetCode 33：逐步演示

LeetCode 33“在旋转排序数组中搜索”是这类问题的经典形式。题目约束保证不存在重复值，并且数组只发生一次旋转。解决方案就是我们之前编写的 search_rotated 函数。面试中的关键要点：始终说明不存在重复值这一假设，在边界处使用具体示例验证不等式，并确认目标值找到和未找到时返回的索引都正确。

# LeetCode 33 — complete solution
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:        # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                            # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

# Tests
print(search([4,5,6,7,0,1,2], 0))   # 4
print(search([4,5,6,7,0,1,2], 3))   # -1
print(search([1], 0))               # -1

LeetCode 153：查找最小值（无重复值）

LeetCode 153“在旋转排序数组中查找最小值”要求在不存在重复值的情况下查找最小值。方法是将 arr[mid] 与 arr[hi]（而不是 arr[lo]）进行比较，以确定最小值位于哪一侧。如果 arr[mid] > arr[hi]，最小值位于右侧；否则最小值位于 mid 或其左侧。这个过程会在 O(log n) 时间内收敛到最小值。

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

print(findMin([3,4,5,1,2]))         # 1
print(findMin([4,5,6,7,0,1,2]))     # 0
print(findMin([11,13,15,17]))       # 11

旋转次数与枢轴索引

找到最小元素后，您也就知道了旋转次数：最小值的索引正好等于数组向右旋转了多少个位置。例如，在 [4,5,6,7,0,1,2] 中，最小值位于索引 4，因此数组向右旋转了 4 个位置。

知道枢轴后，您可以通过将索引对 n 取模来应用标准二分查找：real_idx = (mid + pivot) % n。处理循环索引结构时，这种替代形式可以简化推理。

def search_via_pivot(nums, target):
    n = len(nums)
    # Find pivot (index of minimum)
    lo, hi = 0, n - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    pivot = lo
    # Binary search with offset
    lo, hi = 0, n - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        real_mid = (mid + pivot) % n
        if nums[real_mid] == target:
            return real_mid
        elif nums[real_mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(search_via_pivot([4,5,6,7,0,1,2], 0))  # 4

整合所有内容

在面试中遇到旋转数组问题时，请遵循以下决策树。首先确定您需要查找目标值，还是查找最小值。查找目标值时，使用识别有序半部分的方法。查找最小值时，将 mid 与 hi 进行比较。如果可能存在重复值，请说明最坏情况为 O(n)，并加入缩小边界的备用方案。

请通过在三个经典示例上逐步跟踪代码来练习：不旋转、旋转一次，以及旋转后将最小值置于最后一个位置。

快速检查

检验您对本课数据结构与算法——编程面试准备相关概念的理解。

课程回顾

本课您学到了：旋转后的有序数组始终至少包含一个有序半部分，在决定搜索位置之前，将 arr[lo] 与 arr[mid] 进行比较，以识别哪一半已排序，以及查找最小值时，使用 arr[mid] 与 arr[hi] 的比较来定位旋转枢轴。下一节我们将学习下界和上界二分查找的变体。

常见问题解答

「旋转数组与无序数组中的二分查找」课时是免费的吗？

是的 — 「旋转数组与无序数组中的二分查找」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「旋转数组与无序数组中的二分查找」这节课中我会学到什么？

通过在每一步判断哪一半有序，解决旋转有序数组查找和旋转数组求最小值问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

「旋转数组与无序数组中的二分查找」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 经典二分查找：左、右、中
  2. 旋转数组与无序数组中的二分查找
  3. 下界与上界
  4. 答案空间上的二分查找
← 返回 DSA Interview Prep