C＃
 Computer >> コンピューター >  >> プログラミング >> C＃

C＃での二分探索

バイナリ検索はソートされた配列で機能します。値は配列の中央の要素と比較されます。同等性が見つからない場合は、値が存在しない半分の部分が削除されます。同様に、残りの半分の部分が検索されます。

これが配列のmid要素です。 62を見つける必要があるとしましょう。そうすると、左側の部分が削除され、右側の部分が検索されます-

C＃での二分探索

これらは二分探索の複雑さです-

最悪の場合のパフォーマンス
O（log n）
ベストケースのパフォーマンス
O（1）
平均パフォーマンス
O（log n）
最悪の場合のスペースの複雑さ
O（1）

例

二分探索を実装する方法を見てみましょう-

public static object BinarySearchDisplay(int[] arr, int key) {
   int minNum = 0;
   int maxNum = arr.Length - 1;

   while (minNum <=maxNum) {
      int mid = (minNum + maxNum) / 2;
      if (key == arr[mid]) {
         return ++mid;
      } else if (key < arr[mid]) {
         max = mid - 1;
      }else {
         min = mid + 1;
      }
   }
   return "None";
}

  1. C++での二分木から二分探索木への変換

    二分木 は、ツリーの各ノードが最大2つの子ノードを持つことができる特殊なタイプのツリーです。これらの子ノードは、右の子および左の子と呼ばれます。 単純な二分木は-です 二分探索木（BST） は、次のルールに従う特殊なタイプのツリーです- 左の子ノードの値は常に親よりも小さくなります注 右側の子ノードは、親ノードよりも大きな値を持っています。 すべてのノードが個別に二分探索木を形成します。 二分探索木（BST）の例 − バイナリ検索ツリーは、検索、最小値と最大値の検索などの操作の複雑さを軽減するために作成されます。 ここでは、二分木が与えられており、

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

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