Pythonで二分探索。時間計算量と実際の計算時間をみてみる。

はじめに

Pythonによる二分探索の実装になります。実際の計算時間のグラフものせています。また、線形探索との計算時間の比較グラフものせています。

線形探索がわからない方は、こちらの線形探索の記事からどうぞ。

Pythonで線形探索。計算量と実際の計算時間をみてみる。

目次

二分探索とは？

二分探索(binary search)とは、検索アルゴリズムの一つです。 リストに入っているデータの検索を行います。ソート済みのリストに対して、非常に有効な検索アルゴリズムとなります。 中央の値と検索したい値との比較を行い、検索したい値が中央の値の左にあるか、右にあるかを判断します。 イメージとしては、中央の値との一回の比較により、検索対象のリストが半分になっていくイメージです。ソートされているリストですので、左が小さく、右が大きい。その場合、一回の比較で半分は無効なリストとして判別できます。

二分探索の計算量

時間計算量はです。

データがn個存在するとします。その中央の値を比較対象とすることにより、一回の操作で約半分 (奇数の場合は)に絞られます。nが二倍につき比較回数が一回多くなります。nが四倍なら比較回数が二回多くなります。

下記がのグラフです。値が大きくなるにつれて比較回数が増えなくなるのがわかると思います。1万個のデータで比較回数は最大14回、1億個のデータで比較回数は最大27回となります。

線形探索と比べてみると非常にわかりやすいのですが、線形探索では1億個のデータで比較回数が最大1億回となります。二分探索が線形探索に比べて非常に優秀で、比較回数が劇的に少ないことがわかると思います。

Pythonによる二分探索の実装例

Pythonによる二分探索の実装例となります。リストは0から順に値が代入されているとします。

TARGET = 30000

NUM = 100000000 # 1億個
list = range(NUM) # [0, 1, 2...]

low = 0
high = len(list)

while (low != high): # 検索したい値が存在しない場合は終了
    center = math.floor((low + high) / 2)
    if (list[center] < TARGET):
        low = center + 1
    elif (TARGET < list[center]):
        high = center - 1
    else:
        break # 検索したい値が見つかった

Pythonによる二分探索の実際の計算時間

こちらが10万のリストにたいして、実際にPythonで二分探索を行ったときのグラフとなります。リストのデータ数の増加に対して、計算時間が増加していないことがわかります。

Pythonによる線形探索と二分探索の比較

下記が線形探索と二分探索の、実際の計算時間の比較となります。リストのデータ数の増加に対して、いかに二分探索のほうが優秀かがわかります。