エンジニア実践的基礎: バイナリーサーチ

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

バイナリーサーチとは

バイナリーサーチは対象配列を半分にしながら探索範囲を狭めていくサーチアルゴリズムです。

バイナリーサーチの身近な例は辞書です。辞書は「あ-い-う-…-を-ん」とあいうえお順に並んでします。「なすび」を調べるときどこから開きますか？先頭から順にページをめくるのもいいでしょう。しかし、多くの人は適当に真ん中から開くと思います。なぜなら、「な行」はひらがなのおおよそ真ん中に位置するからです。もし「た行」を開いてしまったら、少し左にページをめくります。「は行」なら逆に右にページをめくります。この操作を繰り返すと「なすび」に辿り着きます。先頭からめくるよりも、より近いページに目星をつけて前後にページをめくる方が効率が良いのは明かです。

バイナリーサーチの実装

バイナリーサーチは配列の探索によく使われます。バイナリーサーチの前提条件として、辞書のようにソートされている必要があります。例えば[1,2,5,10,15,21,22,53,59] という配列から「5」を探索するとします。まず、中央の数字を選びます。中央の数字は「15」です。「15」は「5」より大きいので、「5」は少なくとも左側の部分に存在することがわかります。ここで対象範囲を[1,2,5,10] に絞ります。中央の数字を取得します。今回は中央は「2」です。「2」は「5」より大きいので、右側の「5,10」が対象範囲となります。最後に中央の数字は「5」となり、対象の数字が見つかったので処理は終了します。

def binarySearch(arr, target):
    L, R = 0, len(arr) - 1

    while L <= R:
        mid = (L + R) // 2

        if target > arr[mid]:
            L = mid + 1
        elif target < arr[mid]:
            R = mid - 1
        else:
            return mid
    return -1 # 対象の数字が存在しない場合

計算量

対象範囲を半分に狭めていくので時間計算量は O(logn) です。

まとめ

バイナリーサーチは横文字だと難しそうに感じますが、辞書から単語を見つけるときと同じやり方だと覚えていれば、簡単に理解できます。