Pythonでのバイナリ検索:視覚的な紹介

ようこそ

この記事では、バイナリ検索アルゴリズムが舞台裏でどのように機能するか、そしてそれをPythonで実装する方法を学びます。

特に、次のことを学びます。

  • ターゲット要素を見つけるためにアルゴリズムが舞台裏でどのように機能するか。
  • Pythonの実装が1行ずつどのように機能するか。
  • 線形検索と比較して非常に効率的なアルゴリズムである理由。
  • その利点と要件。

さぁ、始めよう!✨

🔹バイナリ検索の概要

このアルゴリズムは、順序付けられたシーケンス内の要素(リスト、タプル、文字列など)を見つけるために使用されます。

要件

バイナリ検索アルゴリズムをシーケンスに適用するには、シーケンスを昇順で並べ替える必要があります。そうしないと、アルゴリズムは正しい答えを見つけられません。もしそうなら、それは純粋な偶然によるでしょう。

💡ヒント:ニーズに合った並べ替えアルゴリズムを使用して、バイナリ検索を適用する前にシーケンスを並べ替えることができます。

入出力

アルゴリズム(関数として実装)には、次のデータが必要です。

  • 要素の順序付けられたシーケンス(例:リスト、タプル、文字列)。
  • 私たちが探しているターゲット要素。

見つかった場合は、探している要素のインデックスを返します。要素が見つからない場合は、-1が返されます。

効率

すべてのステップでリストの半分を「破棄」できるため、線形検索(最初の要素から1つずつ要素を検索する)と比較して非常に効率的です。

このアルゴリズムに飛び込み始めましょう。

🔸ビジュアルウォークスルー

このリストに二分探索アルゴリズムを適用します。

💡ヒント:リストはすでに並べ替えられていることに注意してください。視覚的な参照としてインデックスが含まれています。

ゴール

整数67のインデックスを見つけたいと思います。

間隔

私たちがアルゴリズムであるとしましょう。プロセスをどのように開始しますか?

まず、検索する区間の2つの境界を選択します。リスト全体を検索したいので、インデックス0を下限として選択し、インデックスを上限として選択します5

ミドルエレメント

次に、この間隔で中央の要素のインデックスを見つける必要があります。これを行うには、下限と上限を加算し、整数除算を使用して結果を2で除算します。

この場合には、(0 + 5)//2ある2結果が原因5/2である2.5と整数除算が小数部分を切り捨て。

したがって、中央の要素はインデックス2にあり、中央の要素は番号6です。

比較

次に、真ん中の要素とターゲット要素の比較を開始して、次に何をする必要があるかを確認する必要があります。

私たちは尋ねます:

真ん中の要素は私たちが探している要素と同じですか?

6 == 67 # False

いいえ、そうではありません。

だから私たちは尋ねます:

真ん中の要素は私たちが探している要素よりも大きいですか?

6 > 67 # False

いいえ、そうではありません。

したがって、中央の要素は、探している要素よりも小さくなります。

6 < 67 # True

要素を破棄する

リストはすでにソートされているので、これは非常に重要なことを教えてくれます。中央の要素の前にあるすべての要素が探している要素よりも小さいことがわかっているため、リストの下半分を「破棄」できることがわかります。したがって、ターゲット要素はそこにありません。

もう一度やり直してください-境界を選択してください

次は何をするの?要素を破棄し、このサイクルを再度繰り返します。

新しい間隔の境界を選択する必要があります(以下を参照)。ただし、上限はそのまま維持され、下限のみが変更されることに注意してください。

これは、探している要素がリストの上半分にある可能性があるためです。上限はそのまま維持され、下限は、ターゲット要素が見つかる間隔に間隔を「縮小」するように変更されます。

💡ヒント:中央の要素が探している要素よりも大きかった場合、上限が変更され、下限はそのまま維持されます。このようにして、リストの上半分を破棄し、下半分で検索を続行します。

ミドルエレメント

次に、下限を上限に追加し、整数除算を使用して結果を2で除算することにより、中間要素のインデックスを見つける必要があります。

の結果(3+5)//24であるため、中央の要素はインデックスに配置され4、中央の要素は67です。

比較

私たちは尋ねます:

真ん中の要素は私たちが探している要素と同じですか?

67 == 67 # True

はい、そうです!したがって、インデックス4の要素が見つかりました。値4が返され、アルゴリズムは正常に完了しました。

💡ヒント:要素が見つからなかった場合、間隔が無効になるまでプロセスが続行されます。リスト全体で要素が見つからなかった場合は、-1が返されます。

🔹コードウォークスルー

アルゴリズムが舞台裏でどのように機能するかを視覚的に理解できたので、Pythonの反復実装について、行ごとに分析してみましょう。

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

ヘッダ

ここに関数ヘッダーがあります:

def binary_search(data, elem):

2つの引数が必要です。

  • 要素の順序付けられたシーケンス(例:リスト、タプル、または文字列)。
  • 見つけたい要素。

初期間隔

次の行は、最初の下限と上限を設定します。

low = 0 high = len(data) - 1

最初の下限はインデックスで0あり、最初の上限はシーケンスの最後のインデックスです。

ループ

有効な間隔があり、下限が上限以下である間、プロセスを繰り返します。

while low <= high:

💡ヒント:境界はインデックスであることを忘れないでください。

ミドルエレメント

すべての反復で、中央の要素のインデックスを見つける必要があります。これを行うには、下限と上限を追加し、整数除算を使用して結果を2で除算します。

middle = (low + high)//2

💡ヒント:リストまたは間隔に偶数の要素が含まれている場合は、整数除算を使用します。たとえば、リストに6つの要素があり、整数除算を使用しなかった場合middle、その結果(0 + 5)/2はになり2.5ます。インデックスを浮動小数点数にすることはできないため、//インデックスの要素を使用して選択することにより、小数部分を切り捨てます2

比較

これらの条件(以下を参照)を使用して、中央の要素の値に応じて何をするかを決定しますdata[middle]。探しているターゲット要素と比較します。

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

3つのオプションがあります。

  • 真ん中の要素が探している要素と等しい場合、その要素が見つかったため、すぐにインデックスを返します。
if data[middle] == elem: return middle
  • 中央の要素が探している要素よりも大きい場合、ターゲット要素がリストの下半分にあることがわかっているため、上限を再割り当てします。
elif data[middle] > elem: high = middle - 1
  • それ以外の場合、残っている唯一のオプションは、中央の要素が探している要素よりも小さいことです。ターゲット要素がリストの上半分にあることがわかっているので、下限を再割り当てします。
else: low = middle + 1

要素が見つかりません

要素が見つからずにループが完了した場合、値-1が返されます。

return -1

そして、バイナリ検索アルゴリズムの最終的な実装があります。

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

🔸特別な場合

これらは、このアルゴリズムを使い始めるときに見つかる可能性のあるいくつかの特定のケースです。

繰り返される要素

探している要素がシーケンス内で繰り返される場合、返されるインデックスは、要素の数と、アルゴリズムがシーケンスに対して実行する操作のシーケンスによって異なります。

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

要素が見つかりません

要素が見つからない場合は、-1が返されます。

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

空のシーケンス

シーケンスが空の場合、-1が返されます。

>>> b = [] >>> binary_search(b, 8) -1

ソートされていないシーケンス

シーケンスがソートされていない場合、答えは正しくありません。正しいインデックスを取得することはまったくの偶然であり、シーケンス内の要素の順序とアルゴリズムによって実行される操作のシーケンスが原因である可能性があります。

この例は正しい結果を返します:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

しかし、これはそうではありません:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

💡ヒント:最初の例が正しい結果を返す理由を考えてください。ヒント:これは、要素の順序は、アルゴリズムが正しいインデックスを到達させるために起こることを、純粋な偶然ですが、ステップバイステップのプロセス評価し0、そして2、最後に6。この特定のケースでは、この特定の要素について、シーケンスがソートされていなくても正しいインデックスが見つかります。

🔹より複雑な例

アルゴリズムとそのPython実装について理解が深まったので、ここではより複雑な例を示します。

バイナリ検索を使用して、このリスト内の要素45のインデックスを検索します。

最初の反復

下限と上限が選択されます。

中央の要素(26)が選択されています。

しかし、真ん中の要素(26)は私たちが探している要素ではなく、45よりも小さいです:

2回目の反復

したがって、中央の要素よりも小さいすべての要素を破棄して、新しい境界を選択できます。新しい下限(27)は、前の中央の要素のすぐ右側にある要素です。

💡ヒント:リストはすでに並べ替えられていることに注意してください。

新しい中央の要素(30)が選択されます。

真ん中の要素(30)は私たちが探している要素ではなく、45よりも小さいです:

3回目の反復

まだ破棄されていない30以下の要素を破棄できます。下限は32に更新されます:

ここに興味深いケースがあります。中央の要素は、であるため、現在の間隔の境界の1つ(7+8)//2です7

真ん中の要素(32)は私たちが探している要素(45)ではなく、小さいです。

4回目の反復

まだ破棄されていない32以下の要素を破棄できます。

ここに、もう1つの非常に興味深いケースがあります。間隔には1つの要素しかありません。

💡ヒント:この間隔はwhile high <= low:、下限のインデックスが上限のインデックスと等しい間隔を含むこの条件を記述したため、有効です。

(8+8)//28であるため、中央の要素が区間内の唯一の要素であるため、中央の要素のインデックスは8で、中央の要素は45です。

今、真ん中の要素は私たちが探している要素です、45

したがって、値8(インデックス)が返されます。

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

🔸エクストラプラクティス

このアルゴリズムをさらに練習したい場合は、このリストに適用して整数90を見つけるときに、アルゴリズムが舞台裏でどのように機能するかを説明してみてください。

[5, 8, 15, 26, 38, 56]
  • ステップバイステップで何が起こりますか?
  • どのような値が返されますか?
  • 要素は見つかりましたか?

あなたが私の記事を気に入ってくれて、それがお役に立てば幸いです。これで、Pythonでバイナリ検索アルゴリズムを実装できます。私のオンラインコース「Pythonの検索と並べ替えのアルゴリズム:実用的なアプローチ」をご覧ください。Twitterでフォローしてください。⭐️