二分探索のバリエーション
01 / 一文での本質
ソート済みの列で、毎ステップ範囲を半分にする—— mid でチェックする述語によって、見つける境界が決まる: 任意の一致、最初の一致、または最後の一致。
問題ソート済み配列で target を探す入力[1, 3, 3, 5, 7, 7, 7, 9, 11]target11モードexact
10
31
32
53
74
75
76
97
118
ソート済み入力、target 11。lo を 0、hi を n−1 に置く —— 閉区間 [lo, hi]。
ステップ
0 / 8
lo · mid · hi
—
区間サイズ
—
結果
—
0 / 8
02 / パターンの骨格
# 完全一致 —— 閉区間 [lo, hi]lo ← 0; hi ← n − 1while lo ≤ hi:mid ← lo + (hi − lo) / 2 // オーバーフロー回避if arr[mid] = target: return midif arr[mid] < target: lo ← mid + 1else: hi ← mid − 1# 最左 —— 半開区間 [lo, hi);厳密な < を非厳密な ≤ に置き換える# 最右 —— 半開区間 [lo, hi);arr[mid] ≤ target を使い、lo − 1 を返す
03 / このパターンを使うべき合図
「ソート済み」
入力がソート済み、あるいはそれと同等に振る舞うよう変換できる。 「半分を捨てる」一手が成り立つのはソート済みだから。
「O(log n)」
期待計算量が半減を示唆している —— ほかの大半の道具は対数時間に届かない。
「最初の / 最後の出現」
欲しいのは任意の一致ではなく境界 —— 出番は 最左 / 最右(lower_bound / upper_bound)。
「答えに対する二分」
答えが数値で、「この値である述語が成り立つか?」を判定できる。 妥当な答えの集合がその値について単調なら —— インデックスではなく値を二分探索する。
04 / よくある落とし穴
i.
(lo + hi) / 2 の整数オーバーフロー。固定幅整数の言語では、配列が大きいと
lo + hi がオーバーフローし得る。 代わりに lo + (hi − lo) / 2 を使う —— 中点は同じで、オーバーフローしない。ii.
閉区間
[lo, hi] と半開区間 [lo, hi) を混ぜる。問題ごとに 1 つの流儀を選び、そのまま貫く。ループ条件(
≤ か <)と境界更新(mid − 1 か mid)が一致しないと、 off-by-one か無限ループになる。iii.
範囲が縮まらない無限ループ。
ある分岐で
lo と hi が変わらない可能性があると、 ループが回り続ける。どの分岐も範囲を厳密に縮めること —— lo = hi のエッジケースについては紙の上で確かめる。05 / LeetCode で練習
4 問、難易度順。最初の 2 つはふつうの二分探索。3 つ目は最左/最右の変種、 4 つ目は「答えに対する二分探索」という発想へ橋渡しする。