バイナリ検索とは何ですか？

ある人が非常に多くの品揃えを持っており、それらを長い列に整然と並べているとします。 その個人は、バイナリ検索を使用することにより、特定のオブジェクトが行のどこにあるかをすばやく把握できます。 この検索は、行の中央のアイテムをチェックし、中央のオブジェクトが探しているアイテムではない場合、その後アイテムが存在する可能性のある行の半分のみを検索することによって行われます。 アイテムは順番に並べられているので、人はどの半分を見続けるかを知っているでしょう。 これらの2つのステップは、アイテムが見つかるか、探す場所がなくなるまで、どんどん小さくなります。

コンピューターサイエンスの分野では、バイナリ検索は、順番に並べ替えられたデータセット内のアイテムの場所（インデックス）を見つける、段階的な手順です。 これは、既知の値を配列の指定された中間要素と比較し、それが等価でない場合、等価性が得られるかリストが使い果たされるまで、中間要素比較をセットの関連する小さい半分に繰り返し制約することでこれを達成します。

半間隔検索とも呼ばれるバイナリ検索は、アイテムのリストの一方の端から開始し、一致が見つかるまで、または検索が最後に達するまで、各アイテムを途中で比較する基本的な順次検索よりもはるかに高速です。リスト。 人が連続して100個のアイテムを持ち、最後のアイテムが検索対象のアイテムである場合、順次検索では100回の比較が必要になります。 ただし、二分法では、アイテムが見つかるまでに最大で7つの比較しか必要ありません。 明らかに、順次検索よりもはるかに効率的です。

バイナリ検索の最大の欠点は、この検索が機能するためにアイテムのリストをソートする必要があることです。 リストのソートには時間がかかります。 ソートしてからこのタイプの検索を使用すると、最初に別のタイプの検索を行うよりも時間がかかる場合があります。

特に非常に大きなデータセットからの情報を使用できることは、生活の中で多くのタスクを達成するために重要です。 コンピュータサイエンスの分野では、有用な結果が得られるように情報を検索する効率的な方法を見つけるなど、多くのタイプの問題を扱っています。 バイナリ検索は、データの検索に使用できる多くのアルゴリズムの1つにすぎません。