線形検索と二分検索の違いは何ですか

検索は、配列などの特定のデータ構造内の要素を検索できるようにする操作です。線形検索と二分検索の2つの検索タイプがあります。線形検索では、配列の要素を1つずつ順番にチェックして、必要なアイテムが配列に存在するかどうかを確認します。一方、バイナリ検索は、アイテムを中央の要素と比較して検索するため、線形検索よりも効率的なアルゴリズムです。

二分探索、線形探索、探索アルゴリズム

線形探索とは

線形検索は単純な検索アルゴリズムです。ここでは、検索は次々とアイテムから行われます。あれは;このアルゴリズムはすべてのアイテムをチェックし、それに一致するアイテムをチェックします。アイテムが存在しない場合、検索はデータの最後まで続行されます。したがって、線形検索は、配列内の各要素を調べて特定のアイテムを見つけることができるアルゴリズムです。

線形検索では、要素を検索するための時間消費または比較の数は、アルゴリズムの効率を決定するのに役立ちます。検索する要素がデータ構造の最初の位置にある場合、必要な比較は1つだけです。必要な要素が最後の位置にある場合、要素を見つけるためにN回の比較が必要です。ここで、Nはデータ項目の数を表します。

二分探索とは

二分探索は高速なアルゴリズムです。ただし、バイナリ検索を実行する前に、データ項目を並べ替える必要があります。コレクションの真ん中のアイテムを比較してアイテムを見つけます。したがって、バイナリ検索では、中間要素を検索し、中間要素を検索する要素と比較する必要があるため、比較回数が少ない特定のアイテムを検索するのにかかる時間が短くなります。

二分探索では、中央の要素が必須要素である場合、そのインデックスが返されます。中央のアイテムが検索されたアイテムよりも高い場合、検索されたアイテムは中央のアイテムの左側のサブ配列にあります。それ以外の場合、アイテムは中央のアイテムの右側のサブ配列にあります。そして、このプロセスは、サブアレイのサイズがゼロになるまでサブアレイで続行されます。このアルゴリズムでは、検索するアイテムの数が毎回減少します。

線形探索と二分探索の違い

意味

線形検索は、一致する要素が見つかるまでリストの要素を順番にチェックすることにより、リスト内の要素を見つけるアルゴリズムです。二分探索は、ソートされた配列内のターゲット値の位置を見つけるアルゴリズムです。したがって、これが線形検索と二分検索の主な違いです。

同義語

シーケンシャル検索は線形検索の別の用語ですが、半間隔検索または対数検索は同じバイナリ検索を指します。

時間の複雑さ

線形検索の時間計算量はO（N）ですが、二分探索の時間計算量はO（log）です。₂NS）。したがって、これは線形探索と二分探索のもう1つの違いです。

最良の場合

さらに、線形検索の最良のケースは最初の位置にある要素を見つけることですが、二分探索の最良のケースは中間の位置にある要素を見つけることです。

配列の並べ替え

線形検索では、要素を検索する前に配列を並べ替える必要はありません。ただし、バイナリ検索では、要素を検索する前に配列を並べ替える必要があります。したがって、配列をソートするための前提条件により、線形検索とバイナリ検索が異なります。

効率

線形検索とバイナリ検索のもう1つの違いは、その効率です。二分探索は線形探索よりも効率的です。

シンプルさ

さらに、二分探索は線形探索よりも複雑です。

結論

線形検索とバイナリ検索は、配列などのデータ構造内の要素を検索するための2つのアルゴリズムです。二分探索は線形探索よりも効率的で高速ですが、検索操作を実行する前に最初に配列をソートする必要があります。したがって、線形検索とバイナリ検索の主な違いは、線形検索と比較した場合、バイナリ検索の方が効率的であり、要素の検索にかかる時間が最小限であるということです。