この記事では、バイナリサーチの背後にある考え方とPythonの実装について掘り下げていきます。
バイナリサーチは、ソートされた配列上で動作する効率的な検索アルゴリズムです。
その直感的な挙動から対数時間(O(logn))で実行されるアルゴリズムの最初の例としてよく利用され、コンピュータサイエンスの基本アルゴリズムとなっています。
バイナリサーチ – 例
バイナリサーチは分割統治アプローチで動作し、配列がソートされていることを利用して、各反復で可能な候補の半分を排除する。
具体的には、ソートされた配列の中央の要素と検索対象の要素を比較し、検索を継続する場所を決定します。
もし目的の要素が真ん中の要素よりも大きければ、それはコレクションの前半に位置することはできないので捨てられる。
その逆も同様です。
注意：配列の要素数が偶数の場合、最初に2つの「真ん中」の要素のどちらを使うかは問題ではありません。
二項探索の仕組みを説明する前に、簡単な例を見てみましょう。
見ての通り、配列はソートされているので、xは元の配列の前半にはないことが確実に分かります。
xが元の配列のどの半分にあるかがわかれば，その半分でこの処理を正確に繰り返し，再び半分に分割して，xを含まないことが確実な半分を捨てればよいのです。
この作業を繰り返し、最終的に1つの要素しか含まない部分配列ができます。
その要素がxであるかどうかを調べます。
xであればxを見つけたことになり、xでなければxは配列の中に存在しません。
これをよく見てみると、最悪の場合（xが配列に存在しない場合）には、ソートされていない配列の場合よりもはるかに少ない数の要素をチェックする必要があることに気づきます。
より正確には、最悪の場合、チェックする要素数はlog2N（Nは配列の要素数）です。
これは、配列が大きくなればなるほど、大きな影響を及ぼします。
となります。
仮に配列の要素数が10個だった場合、xを見つけるか、存在しないと判断するために必要な要素数は3個だけです。
これは33.3%です。
しかし、配列の要素が10,000,000個あった場合、24個の要素をチェックするだけでよいのです。
これは0.0002%です。
バイナリサーチの実装
バイナリサーチは、サイズ1の配列が見つかるまで、どんどん小さな配列に対して同じ処理を繰り返すので、当然ながら再帰的なアルゴリズムです。
しかし、もちろん反復的な実装もあり、ここでは両方のアプローチを紹介します。
再帰的
まずは、再帰的な実装の方が自然なので、再帰的な実装から始めてみましょう。
def binary_search_recursive(array, element, start, end):
if start > end:
return -1
mid = (start + end) // 2
if element == array[mid]:
return mid
if element < array[mid]:
return binary_search_recursive(array, element, start, mid-1)
else:
return binary_search_recursive(array, element, mid+1, end)
このコードを詳しく見てみましょう。
start要素がend` 要素より大きい場合、再帰を終了する。
if start > end:
return -1
これは、この状況が配列に要素が存在しない場合にのみ発生するからです。
何が起こるかというと、現在の部分配列の中に要素が1つしかなく、その要素が探している要素に一致しないということになります。
この時点で、 start は end と等しくなります。
しかし、 element は array[mid] と等しくないので、 end を 1 つ減らすか、 start を 1 つ増やすように配列を再び「分割」し、その条件下で再帰を実行します。
これは別のアプローチでも可能でした。
if len(array) == 1:
if element == array[mid]:
return mid
else:
return -1
残りのコードでは、「中央の要素をチェックし、配列の適切な半分を検索し続ける」ロジックを実行します。
真ん中の要素のインデックスを見つけ、探している要素がそれにマッチするかどうかをチェックします。
mid = (start + end) // 2
if elem == array[mid]:
return mid
一致しない場合は、その要素が真ん中の要素より小さいか大きいかを調べます。
if element < array[mid]:
# Continue the search in the left half
return binary_search_recursive(array, element, start, mid-1)
else:
# Continue the search in the right half
return binary_search_recursive(array, element, mid+1, end)
このアルゴリズムに少し手を加えて、現在どの部分配列で作業しているかを出力するようにして実行してみましょう。
element = 18
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
print("Searching for {}".format(element))
print("Index of {}: {}".format(element, binary_search_recursive(array, element, 0, len(array))))
このコードを実行すると、次のような結果になります。
Searching for 18
Subarray in step 0:[1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1:[16, 18, 24, 28, 29]
Subarray in step 2:[16, 18]
Subarray in step 3:[18]
Index of 18: 7
繰り返しのたびに探索空間が半分になり、探している要素にどんどん近づいていく様子がよくわかります。
もし、配列の中に存在しない要素を探そうとすると、次のような出力になります。
Searching for 20
Subarray in step 0: [4, 14, 16, 17, 19, 21, 24, 28, 30, 35, 36, 38, 39, 40, 41, 43]
Subarray in step 1: [4, 14, 16, 17, 19, 21, 24, 28]
Subarray in step 2: [19, 21, 24, 28]
Subarray in step 3: [19]
Index of 20: -1
面白いので、大きな配列を検索して、ある数字が存在するかどうかをバイナリサーチが判断するのに何ステップかかるか見てみましょう。
Searching for 421, in an array with 200 elements
Search finished in 6 steps. Index of 421: 169
Searching for 1800, in an array with 1500 elements
Search finished in 11 steps. Index of 1800: -1
Searching for 3101, in an array with 3000 elements
Search finished in 8 steps. Index of 3101: 1551
反復的
反復的なアプローチは非常にシンプルで、再帰的なアプローチに似ています。
ここでは、whileループの中でチェックを行うだけです。
def binary_search_iterative(array, element):
mid = 0
start = 0
end = len(array)
step = 0
while (start <= end):
print("Subarray in step {}: {}".format(step, str(array[start:end+1])))
step = step+1
mid = (start + end) // 2
if element == array[mid]:
return mid
if element < array[mid]:
end = mid - 1
else:
start = mid + 1
return -1
配列に値を入力して、その中のある要素を探してみましょう。
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
print("Searching for {} in {}".format(element, array))
print("Index of {}: {}".format(element, binary_search_iterative(array, element)))
このコードを実行すると、次のような出力が得られます。
Searching for 18 in [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 0: [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1: [16, 18, 24, 28, 29]
Subarray in step 2: [16, 18]
Subarray in step 3: [18]
Index of 18: 7
結論
バイナリサーチは、大きなソート済み配列や、1つの配列の中の要素を繰り返し検索する場合に、非常に有効なアルゴリズムです。
配列を一度ソートしてからバイナリサーチを使って何度も要素を探すコストは、ソートされていない配列に対して線形探索を使ってソートのコストを回避するよりもはるかに優れています。
配列のソートと要素の検索を一度だけ行うのであれば、ソートされていない配列に対して線形探索を行った方が効率的です。
Pythonのソートアルゴリズムについて読みたい方は、こちらをご覧ください。