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

人が非常に多数のアイテムを持っており、長い列に整然と整理されているとします。その個人は、バイナリ検索を使用して特定のオブジェクトがどこにあるかをすぐに把握できます。この検索は、行の中央のアイテムをチェックすることによって行われ、中央のオブジェクトが求められているアイテムではない場合、その後、アイテムが可能な行の半分の1つだけを調べます。人は、アイテムが順番に配置されているため、どの半分を調べ続けるかを知っているでしょう。これらの2つのステップは、アイテムが見つかるか、見た目が残っていないようになるまで、ますます小さい半分で何度も行われます。

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

半分間隔検索と呼ばれるバイナリ検索は、アイテムのリストの一方の端から始まり、試合が見つかるまで、または検索がリストの終わりに達するまで途中で各アイテムを比較する基本的なシーケンシャル検索よりもはるかに高速です。人が100個のアイテムを連続して持っていて、最後のアイテムが探しているものである場合、シーケンシャル検索では100の比較が必要です。ただし、二等分法では、アイテムが見つかる前に最大で7つの比較のみが必要です。それは明らかにシーケンシャル検索よりもはるかに効率的です。

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

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