本記事では備忘録ブログ初投稿テストも兼ねて、「Python」での二分探索の実装方法について書いていきます。
詳細は後に回し、まず先にコードを見てみます。
二分探索コード
下記のbinary_search()関数は、第一引数に数値のソート済みリスト、第二引数に探索したい数値を渡すと、そのターゲットの数値の位置を返します。(indexは0からです。)
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
mid = (left + right) // 2
if data[mid] == target:
return mid
elif data[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
data = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
print(binary_search(data, 70))
[参考: Pythonではじめるアルゴリズム入門]
二分探索とは？
二分探索とは、データ検索アルゴリズムの一つです。ソート済みのデータ群において、探索したいデータが中央の要素より大きいか小さいかを調べ、探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法です。計算量はO(logn)です。
[参考: IT用語辞典 e-Words]
ソートについて
今回のbinary_search()関数は、渡されるデータ群がソート済みの前提で書かれています。次回以降の記事では、ソートの方法の種類や計算量比較を行いたいと思います。