二分探索パターン

古典的な二分探索 - 簡単なレビュー

二分探索では、ステップごとに探索空間が半分になります。 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 を達成できますか?」と尋ねます。 「はい」の場合は、より小さくしてみてください。いいえの場合は、より大きくしてみてください。

例: バナナを食べるココ

ココにはバナナが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 を比較してどちらの半分かを決定し、ターゲットがソートされた半分に該当するかどうかを確認します。