二分探索法 （Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、探索アルゴリズムの中の二分探索法（Binary Search）について学んでいきます。

二分探索法とは

二分探索法（Binary Search）とは、予め整列（ソート）されているリストに対して特定のデータを探索するアルゴリズムです。

もしn個のデータを登録している場合、探索する度にその範囲は1/2になるので、その計算量はO(log n)となります。

線形探索法に比べて効率の良いアルゴリズムですが、予め整列済みのデータであるという条件があるため、データの登録と探索を頻繁に実行するような用途には向きません。

Pythonで二分探索を作ってみる

それでは、Pythonで二分探索を実装してみます。

# binary_search.py
def binary_search(sequence, target):
    length = len(sequence)
    low = 0
    high = length - 1
    while low <= high:
        middle = int((low + high) / 2)
        if target == sequence[middle]:
            return middle
        elif target < sequence[middle]:
            high = middle - 1
        elif target > sequence[middle]:
            low = middle + 1
    return None

seq = [1,3,4,8,13,14,18,20,21,25]
target = 8
result = binary_search(seq, target)
if result:
    print("{} at position: {}.".format(target, result))
else:
    print('{} not in sequence.'.format(target))

動作確認

それでは上記で作成したスクリプトを実行してみます。

 > python binary_search.py
 8 at position: 3.

対象のインデックスを取得することができました。

特にデータを追加登録する必要がない場合は、まず既存データの順序を無視して登録をし、その後にクイックソートで整列をすれば、計算量はO(n log n)まで減らすことができるので、扱うデータ数や用途を考慮する必要があります。

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)