二分探索アルゴリズムと例

二分探索を学ぶ前に、次のことを学びましょう。

検索とは何ですか?

検索は、ユーザーがデータベース内に保持されているドキュメント、ファイル、メディア、またはその他の種類のデータを検索できるようにするユーティリティです。 検索は、基準とレコードを照合し、それをユーザーに表示するという単純な原理に基づいて機能します。 このようにして、最も基本的な検索機能が機能します。

二分探索とは何ですか?

二分検索は、並べ替えられた項目のリストからデータを検索してフェッチする、高度なタイプの検索アルゴリズムです。 その中心的な動作原理には、必要な値が特定され、検索結果でユーザーに表示されるまで、リスト内のデータを半分に分割することが含まれます。 二分探索は一般に 半間隔検索 または 対数検索.

二分探索はどのように機能するのでしょうか?

二分探索は次のように機能します。wing マナー:

  • 検索プロセスは、ソートされたデータ配列の中央の要素を見つけることで開始されます。
  • その後、キー値と要素が比較されます。
  • キー値が中央の要素より小さい場合、検索は比較および照合のために中央の要素までの上位の値を分析します。
  • キー値が中央の要素より大きい場合は、比較および照合のために中央の要素までの低い値を検索分析します。

二分探索の例

辞書の例を見てみましょう。 特定の単語を見つける必要がある場合、誰も各単語を順番に調べるのではなく、ランダムに単語を見つけます。arest 単語で必要な単語を検索します。

二分探索の例

上の画像は次のことを示していますwing:

  1. 10 桁の配列があり、要素 59 を見つける必要があります。
  2. すべての要素には 0 ~ 9 のインデックスが付けられます。ここで、配列の中央が計算されます。 これを行うには、インデックスの左端と右端の値を取得して 2 で割ります。結果は 4.5 ですが、下限値を取得します。 したがって、真ん中は4になります。
  3. 4 は 59 より大きいため、アルゴリズムは中央 (24) から下限までのすべての要素を削除し、配列には 5 つの要素だけが残ります。
  4. ここで、59 は 45 より大きく、63 より小さいです。中央は 7 です。したがって、右側のインデックス値は中央 – 1 (6 と等しくなります) になり、左側のインデックス値は以前と同じ 5 になります。
  5. この時点で、59 の後に 45 が来ることがわかります。したがって、左側のインデックス (5) も Mid になります。
  6. これらの繰り返しは、配列が XNUMX つの要素のみに減らされるか、検索される項目が配列の中央になるまで続きます。

続きを見てみましょうwing 二分探索の動作を理解するための例

二分探索の例

  1. 2 ~ 20 の範囲で並べ替えられた値の配列があり、18 を見つける必要があります。
  2. 下限値と上限値の平均は、(l + r) / 2 = 4 です。検索されている値は、中央の 4 よりも大きくなります。
  3. 中央値より小さい配列値は検索から除外され、中央値 4 より大きい値が検索されます。
  4. これは、実際の検索対象が見つかるまで繰り返し分割されるプロセスです。

なぜ二分探索が必要なのでしょうか?

次のことwing 二分検索が検索アルゴリズムとして使用するのに適した選択肢である理由は次のとおりです。

  • 二分検索は、データのサイズに関係なく、並べ替えられたデータに対して効率的に機能します。
  • データを順番に調べて検索を実行する代わりに、バイナリ アルゴリズムはデータにランダムにアクセスして必要な要素を見つけます。 これにより、検索サイクルが短縮され、より正確になります。
  • 二分検索は、速度が遅く、ほとんど不正確な等価比較を使用するよりも、順序付けの原則に基づいて並べ替えられたデータの比較を実行します。
  • 検索の各サイクルの後、アルゴリズムは配列のサイズを半分に分割するため、次の反復では配列の残りの半分でのみ機能します。

次のチュートリアルを学習してください 線形検索: Python、C++ の例

まとめ

  • 検索は、ユーザーがドキュメント、ファイル、その他の種類のデータを検索できるようにするユーティリティです。 二分検索は、並べ替えられた項目のリストからデータを検索してフェッチする、高度なタイプの検索アルゴリズムです。
  • 二分探索は、一般に半区間探索または対数探索として知られています。
  • これは、必要な要素が見つかった場合の反復ごとに配列を半分に分割することで機能します。
  • また, バイナリアルゴリズム は、左端と右端のインデックス値の合計を 2 で割ることにより、配列の中央を取得します。今度は、アルゴリズムは、検索する要素に応じて、配列の中央から要素の下限または上限を削除します。
  • アルゴリズムはデータにランダムにアクセスして、必要な要素を見つけます。 これにより、検索サイクルが短縮され、より正確になります。
  • 二分検索では、時間がかかり不正確な等価比較を使用するのではなく、順序付けの原則に基づいて並べ替えられたデータの比較が実行されます。
  • 二分検索は、並べ替えられていないデータには適していません。