C ++プログラムでの二分探索？

二分探索は、半区間探索、対数探索、または二分探索とも呼ばれ、ソートされた配列内のターゲット値の位置を見つける検索アルゴリズムです。二分探索は、ターゲット値を配列の中央の要素と比較します。それらが等しくない場合、ターゲットが存在できない半分が削除され、残りの半分で検索が続行され、再び中央の要素がターゲット値と比較され、ターゲット値が見つかるまでこれが繰り返されます。残りの半分が空の状態で検索が終了した場合、ターゲットは配列に含まれていません。アイデアは単純ですが、バイナリ検索を正しく実装するには、特に配列の値が範囲内の整数のすべてではない場合、終了条件と中間点の計算に関する微妙な点に注意する必要があります。

二分探索は最も人気のある検索アルゴリズムです。これは効率的であり、問​​題を解決するために使用される最も一般的に使用される手法の1つでもあります。

世界のすべての名前が順番に書き留められていて、特定の名前の位置を検索したい場合、バイナリ検索は最大35回の反復でこれを実行します。

二分探索は、ソートされた要素のセットに対してのみ機能します。コレクションでバイナリ検索を使用するには、最初にコレクションを並べ替える必要があります。

二分探索を使用してソートされたセットに対して操作を実行する場合、検索される値に基づいて反復回数を常に減らすことができます。

次の配列を考えてみましょう-

線形探索を使用することにより、要素8の位置が9回目の反復で決定されます。

二分探索を使用して反復回数を減らす方法を見てみましょう。検索を開始する前に、範囲の開始と終了を知る必要があります。それらを低と高と呼びましょう。

Low = 0
High = n-1

次に、検索値Kを、下限と上限の中央値にある要素と比較します。値Kが大きい場合は下限を増やし、そうでない場合は上限を減らします。

上の画像を参照すると、下限は0、上限は9です

下限と上限の中央値は（lower_bound + upper_bound）/ 2=4です。ここでa[4]=4です。値4>2は、検索する値です。したがって、4を超える要素は明らかに2を超えるため、4を超える要素を検索する必要はありません。

したがって、配列の上限を要素4の位置にいつでもドロップできます。ここで、次の値を使用して、同じ配列で同じ手順に従います-

Low: 0
High: 3

Low> Highになるまで、この手順を再帰的に繰り返します。いずれかの反復でa[mid]=keyを取得した場合、midの値を返します。これは、配列内のキーの位置です。キーが配列に存在しない場合は、-1を返します。

例

int binarySearch(int low,int high,int key){
   while(low<=high){
      int mid=(low+high)/2;
      if(a[mid]<key){
         low=mid+1;
      }
      else if(a[mid]>key){
         high=mid-1;
      }
      else{
         return mid;
      }
   }
   return -1; //key not found
}