Binary Search

目的

ソート済みデータから要素を効率的に見つけ、探索に対数の計算量を適用する。

メカニズム

区間 [lo, hi] を保ち、mid=(lo+hi)/2 とする。mid と目的の値を比較し、等しければ返し、目的の値が大きければ右半分を、小さければ左半分を探索する。区間は各ステップで半分になり、O(log n) となる。ソート済みであることが前提である。変種として下限、上限、挿入位置の探索がある。

ユースケース

• ソート済み配列の検索
• データベースの B+ 木インデックス
• バージョン管理の bisect
• 関数のゼロ点探索（バイセクション法）

例

• 入力

  Search 5 in [1,3,5,7,9]

  Output

  Index 2

  2 comparisons

よくあるエラー

lo+hi integer overflow

Use lo+(hi-lo)/2