二分搜索模式

经典二分搜索 - 快速回顾

二分搜索每一步将搜索空间减半。在 n 个元素的排序数组上，它在 O(log n) 时间内找到目标。

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

简单 - 但二分搜索的真正威力远远超出了排序数组。

搜索空间概念

只要您在某个范围内有单调条件，二分搜索就会起作用。 “数组”甚至不需要存在 - 你只需要一个范围 [lo, hi] 和一个在某个边界从 False 翻转到 True （反之亦然）的函数。

Search space:  [lo .................. hi]
Condition:      F  F  F  F  T  T  T  T
                          ^-- answer

对答案进行二分查找

不要搜索数组，而是搜索答案空间。问：“我能达到结果 X 吗？”如果是，请尝试较小的；如果没有，请尝试更大的。

示例：Koko 吃香蕉

Koko 有 n 堆香蕉和 h 小时。找到最小进食速度，以便她及时吃完。

def min_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        hours = sum((p + mid - 1) // mid for p in piles)
        if hours <= h:
            hi = mid      # speed works, try slower
        else:
            lo = mid + 1  # too slow, go faster
    return lo

答案空间是 [1, max(piles)] 并且条件是单调的 - 更高的速度总是意味着更少的时间。

旋转排序数组

已排序的数组在某个枢轴处旋转：[4, 5, 6, 7, 0, 1, 2]。一半总是排序的。比较 mid 和 lo 来决定哪一半，然后检查目标是否属于已排序的一半。

[4, 5, 6, 7, 0, 1, 2]
 L        M        R
Left half [4..7] is sorted.
Target 1 not in [4..7] → search right.