二分探索のバリエーション

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 / よくある落とし穴

(lo + hi) / 2 の整数オーバーフロー。
固定幅整数の言語では、配列が大きいと lo + hi がオーバーフローし得る。 代わりに lo + (hi − lo) / 2 を使う —— 中点は同じで、オーバーフローしない。
閉区間 [lo, hi] と半開区間 [lo, hi) を混ぜる。
問題ごとに 1 つの流儀を選び、そのまま貫く。ループ条件(≤ か <)と境界更新(mid − 1 か mid)が一致しないと、 off-by-one か無限ループになる。
範囲が縮まらない無限ループ。
ある分岐で lo と hi が変わらない可能性があると、 ループが回り続ける。どの分岐も範囲を厳密に縮めること —— lo = hi のエッジケースについては紙の上で確かめる。

05 / LeetCode で練習

簡単8

01Search Insert Position— LC 35→02Sqrt(x)— LC 69→03First Bad Version— LC 278→04Valid Perfect Square— LC 367→05Guess Number Higher or Lower— LC 374→06Binary Search— LC 704→07Find Smallest Letter Greater Than Target— LC 744→08Kth Missing Positive Number— LC 1539→

中級25

01Search in Rotated Sorted Array— LC 33→02Find First and Last Position of Element in Sorted Array— LC 34→03Pow(x, n)— LC 50→04Search a 2D Matrix— LC 74→05Search in Rotated Sorted Array II— LC 81→06Find Minimum in Rotated Sorted Array— LC 153→07Find Peak Element— LC 162→08Search a 2D Matrix II— LC 240→09Find the Duplicate Number— LC 287→10Longest Increasing Subsequence— LC 300→11Kth Smallest Element in a Sorted Matrix— LC 378→12Random Pick with Weight— LC 528→13Single Element in a Sorted Array— LC 540→14Find K Closest Elements— LC 658→15K-th Smallest Prime Fraction— LC 786→16Peak Index in a Mountain Array— LC 852→17Koko Eating Bananas— LC 875→18Time Based Key-Value Store— LC 981→19Capacity To Ship Packages Within D Days— LC 1011→20Find the Smallest Divisor Given a Threshold— LC 1283→21Minimum Number of Days to Make m Bouquets— LC 1482→22Minimum Limit of Balls in a Bag— LC 1760→23Maximum Candies Allocated to K Children— LC 2226→24Successful Pairs of Spells and Potions— LC 2300→25Minimize the Maximum Difference of Pairs— LC 2616→

難しい8

01Median of Two Sorted Arrays— LC 4→02Find Minimum in Rotated Sorted Array II— LC 154→03Russian Doll Envelopes— LC 354→04Split Array Largest Sum— LC 410→05Kth Smallest Number in Multiplication Table— LC 668→06Find K-th Smallest Pair Distance— LC 719→07Nth Magical Number— LC 878→08Find in Mountain Array— LC 1095→