データ構造とアルゴリズム二分探索

二分探索は、実行時の複雑さがΟ（log n）の高速検索アルゴリズムです。この検索アルゴリズムは、分割統治の原則に基づいて機能します。このアルゴリズムが正しく機能するためには、データ収集がソートされた形式である必要があります。

バイナリ検索では、コレクションの真ん中のアイテムを比較して特定のアイテムを検索します。一致する場合は、アイテムのインデックスが返されます。中央のアイテムがアイテムよりも大きい場合、アイテムは中央のアイテムの左側にあるサブ配列で検索されます。それ以外の場合、アイテムは中央のアイテムの右側のサブ配列で検索されます。このプロセスは、サブアレイのサイズがゼロになるまでサブアレイでも続行されます。

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

バイナリ検索が機能するためには、ターゲット配列をソートする必要があります。絵の例で二分探索のプロセスを学びます。以下はソートされた配列であり、バイナリ検索を使用して値31の場所を検索する必要があると仮定します。

まず、次の式を使用して配列の半分を決定します。

mid = low + (high - low) / 2

これは、0 +（9-0）/ 2 = 4（整数値4.5）です。したがって、4は配列の中央です。

ここで、場所4に格納されている値を、検索されている値、つまり31と比較します。場所4の値は27であり、一致していません。値が27より大きく、配列が並べ替えられているため、ターゲット値が配列の上部にある必要があることもわかっています。

低値を中値+1に変更し、新しい中値を再度見つけます。

low = mid + 1
mid = low + (high - low) / 2

私たちの新しいミッドは今7です。ロケーション7に格納されている値をターゲット値31と比較します。

場所7に格納されている値は一致していませんが、探している値を超えています。したがって、値はこの場所から下部にある必要があります。

したがって、中間を再度計算します。今回は5です。

ロケーション5に保存されている値をターゲット値と比較します。一致していることがわかります。

目標値31は場所5に格納されていると結論付けます。

二分探索は検索可能な項目を半分にするため、比較の数が非常に少なくなります。

擬似コード

二分探索アルゴリズムの擬似コードは次のようになります-

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Cプログラミング言語で配列を使用したバイナリ検索の実装については、ここをクリックしてください。