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

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

検索とは何ですか?

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

バイナリ検索は、ソートされた項目のリストからデータを検索して取得する高度なタイプの検索アルゴリズムです。その基本的な動作原理は、必要な値が見つかり、検索結果でユーザーに表示されるまで、リスト内のデータを半分に分割することです。バイナリ検索は一般に 半間隔検索 または 対数検索.

バイナリ検索は次のように動作します。

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

上の画像は、次のことを示しています。

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

二分探索の仕組みを理解するために次の例を見てみましょう。

以下の理由により、バイナリ検索は検索アルゴリズムとして使用するのに適した選択肢となります。

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

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

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

よろしければ：