本日は、非常に高速な検索アルゴリズムであるバイナリサーチアルゴリズムをPythonで学びます。
その論理、Pythonでの書き方、そして何がそんなに速いのかを見ていきます。
バイナリサーチアルゴリズム
このアルゴリズムでは、与えられたリストがソートされていることが必要です。
これは、ある数字がリストの中で特定の他の数字の後にあるか前にあるかを、リストのソートに基づいて見つけることができるからです。
辞書の単語や本のページ番号を調べる方法を思い出してください。
辞書の単語や本のページ番号を探すとき、ある地点に行き、その地点の後なのか前なのかを確認し、目的のものを見つけるまでこのような推理を繰り返す。
同じように、バイナリサーチでは、まずリストの中心を探します。
そこで項目が見つかり、アルゴリズムが終了するか、リストの並べ方から項目が真ん中の項目の後か前かがわかるか、どちらかです。
この後、必要な項目がないと思われる半分の項目は単に無視することにします。
そして、この作業をもう半分の真ん中まで繰り返す。
最終的に、項目が見つかるか、排除する半分がなくなるかで、このアルゴリズムは成功または失敗のどちらかで終了します。
リストを2つに分割し、片方を削除していることに注意してください。
このようなアルゴリズムの動作から、バイナリサーチと名付けられました。
メリアム-ウェブスター辞書の「バイナリ」の意味：正反対とみなされる2つのグループまたはクラスに分割すること。
おすすめの読み物 Pythonによる二分探索木アルゴリズム
バイナリサーチアルゴリズムの理論的な例
例題を挙げて理解を深めよう。
与えられたリスト。
- リストには9つの項目があるので、中央のものは位置5にあるはずで、それは51です。
- 51は23と等しくないが、23より多い。51は23と等しくはありませんが、23より大きいので、もし23がリストにあれば、51より前にあるはずです。そこで、51とそれ以降のすべての項目を削除します。
- 残りのリスト。11, 23, 36, 47
- 今、リストには4つの項目があり、中心指数の計算方法によって、2が中心位置であることも、3が中心位置であることもわかります。
- 簡単のために、開始位置と終了位置の平均を計算して中心を求めます。
- ここでは、開始位置＝1、終了位置＝4なので、平均は2（2.5の整数部）です。
- つまり、2の位置には23があり、これが求めるべき項目です。そして、アルゴリズムが終了し、ターゲットの位置が得られます。
では、バイナリサーチのアルゴリズムがPythonでどのようにコード化されるかを見てみましょう。
Python によるバイナリサーチ
def binary_search(lst, target):
start = 0
end = len(lst) - 1
while(start <= end):
mid = (start + end) // 2
if(lst[mid] > target):
end = mid - 1
elif(lst[mid] < target):
start = mid + 1
else:
return mid
return None
|
それでは、アルゴリズムを見ていきましょう。
- 最初の引数はリストで、2番目の引数は検索するターゲットです。
- 2つの変数
startとendを宣言し、それぞれリストの先頭 (0) と末尾 (length – 1) を指します。 - この2つの変数は、この範囲外のアイテムは考慮されないので、検索からアイテムを排除する役割を担っています。
- 次のループでは、開始点が終了点以下である限り、項目の検索と削除を続けます。なぜなら、開始点が終了点より大きくなるのは、項目がリストにない場合だけだからです。
- ループの内部では、
startとendの平均の整数値を求め、それをリストの真ん中の項目と見なします。
ここで、もし真ん中の項目がターゲットよりも大きければ、ターゲットは真ん中の項目の前にしか存在できないことを意味します。
そこで、リストの末尾を真ん中より前のインデックスとし、こうすることで、midを含むmid以降のインデックスはすべて考慮から外れます。
同様に、真ん中の項目がターゲットよりも小さい場合、ターゲットは真ん中の項目の後にしか存在できないことを意味します。
インデックス mid と mid より前のすべてのインデックスを排除するために、変数 start を mid より後のインデックスに設定します。
上の2つのケースのいずれにも当てはまらない場合、つまり、真ん中のアイテムがターゲットより大きくも小さくもない場合、それはターゲットでなければならない。
そこで、単純にこの真ん中のアイテムのインデックスを返して、アルゴリズムを終了させる。
もしループが終了したら、それはターゲットが見つからなかったことを意味します。
これはターゲットがリストの中になかったことを意味し、この関数は単に None を返します。
では、実際にコードを実行して、その出力を確認してみましょう。
結果は以下の通りです。
23 はリスト numbers に存在するので、この関数はそのインデックスである 2 を返しますが、70 はリストに存在しないので、この関数は None を返します。
バイナリサーチを高速化する理由
線形探索のような単純な探索アルゴリズムでは、探しているものを見つけるまで各項目を通過しなければなりません。
つまり、入力サイズが大きくなると、入力サイズが大きくなるのと同じだけ、項目を見つけるのにかかる時間が長くなります。
定量的には、その時間複雑度はO(n)です。
時間計算量とは、あるアルゴリズムがどれだけ速いか、あるいは効率的かを数値化する方法です。
バイナリサーチの場合、その時間計算量は「O(log2n)」であり、入力リストのサイズが2倍になれば、アルゴリズムは1回余分に反復を行うだけということになる。
同様に、入力のサイズが1000倍になれば、ループはあと10回実行されればよいことになる。
繰り返しのたびにリストの半分が削除されるので、リスト全体が削除されるのにそれほど時間はかからないことを思い出してください。
まとめ
この記事では、バイナリサーチとは何か、その名前の由来、バイナリサーチが具体的に何をするのか、そしてなぜそんなに速いのかについて学びました。
また、時間複雑性の観点からその効率性を議論し、Pythonでどのようにコーディングするかを見てきました。
バイナリサーチは多くの検索アルゴリズムの一つであり、最も高速な検索アルゴリズムの一つです。
バイナリサーチについて楽しく学んでいただけたら幸いです。
また次のチュートリアルでお会いしましょう。