本記事は、ソフトバンクパブリッシングから発行されている「定本 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)
