Pythonでの二分探索の説明

二分探索は、ソートされた配列から要素を検索するために使用される検索アルゴリズムです。ソートされていない配列からの検索には使用できません。二分探索は効率的なアルゴリズムであり、時間計算量の点で線形探索よりも優れています。

線形探索の時間計算量はO（n）です。一方、二分探索の時間計算量はO（log n）です。したがって、二分探索は効率的で高速な検索アルゴリズムですが、ソートされた配列からの検索にのみ使用できます。

バイナリ検索はどのように機能しますか？

二分探索の背後にある基本的な考え方は、必要な要素を配列のすべての要素と比較する代わりに、必要な要素を配列の中央の要素と比較することです。これが私たちが探している要素であることが判明した場合、検索は正常に完了しています。それ以外の場合、探している要素が中央の要素よりも小さい場合、配列は並べ替えられているため、要素が配列の前半分または左半分にあることが確実です。同様に、探している要素が中央の要素よりも大きい場合は、その要素が配列の後半にあることを確認してください。

したがって、二分探索は配列を継続的に半分に減らします。上記のプロセスは、探している要素が見つかるまで、配列の選択された半分に再帰的に適用されます。

左のインデックスが0で、右のインデックスが配列の最後のインデックスに等しい状態で検索を開始します。中央の要素のインデックス（mid）が計算されます。これは、左右のインデックスの合計を2で割ったものです。必要な要素が中央の要素よりも小さい場合、右側のインデックスはmid-1に変更されます。これは、次のことを意味します。アレイの前半のみを見てください。同様に、必要な要素が中央の要素よりも大きい場合、左側のインデックスはmid + 1に変更されます。これは、配列の後半のみを確認することを意味します。選択したアレイの半分に対して上記のプロセスを繰り返します。

要素が配列に存在しないかどうかをどのように知ることができますか？

さらに検索を停止するには、要素が配列に存在しないことを示す条件が必要です。左側のインデックスが右側のインデックス以下である限り、配列内の要素を繰り返し検索します。この条件がfalseになり、要素がまだ見つからない場合、これは要素が配列に存在しないことを意味します。

例

次の並べ替えられた配列を取得して、要素6を検索する必要があります。

L =0 H =8 Mid =4

6 <10なので、前半を取ります。

H=ミッド-1

L =0 H =3 Mid =1

6> 5なので、後半を選択します。

L=ミッド+1

L =2 H =3 Mid =2

6 ==6、見つかった要素

したがって、要素6はインデックス2にあります。

実装

指定された並べ替えられた配列から、必要な要素を検索し、その要素が配列に存在する場合はそのインデックスを出力します。要素が存在しない場合は、-1を出力します。

二分探索を実装するためのコードを以下に示します。

例

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

出力

6
-1

要素7はインデックス6に存在します。

要素15が配列に存在しないため、-1が出力されます。