Data-structures-algorithms-binary-search-algorithm

データ構造とアルゴリズムのバイナリ検索

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

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

バイナリ検索の仕組み

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

バイナリ検索

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

mid = low + (high - low)/2

ここでは、0＆plus;です。 （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に格納されている値は一致ではなく、探している値以上のものです。 そのため、値はこの場所から下部になければなりません。

バイナリ検索

したがって、midを再度計算します。 今回は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 &plus; ( upperBound - lowerBound )/2

      if A[midPoint] < x
         set lowerBound = midPoint &plus; 1

      if A[midPoint] > x
         set upperBound = midPoint - 1

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

end procedure

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