線形探索と二分探索の主な違いは、二分探索（半値探索または対数探索とも呼ばれる）は線形探索（または順次探索）よりも効率的で、要素の探索にかかる時間が最短であることである。
探索とは、配列のような特定のデータ構造から要素を探し出す操作です。
検索には、線形検索とバイナリ検索の2種類があります。
線形探索は、配列の要素を1つずつ順番にチェックし、必要な項目が配列内に存在するかどうかを探します。
一方、バイナリサーチは、途中の要素と比較して項目を検索するため、線形探索よりも効率的なアルゴリズムです。
リニアサーチとは
線形探索は、単純な探索アルゴリズムです。
ここでは、1つの項目から順に検索を行います。
つまり、このアルゴリズムは、すべての項目をチェックし、その項目に一致するものがあるかどうかを調べます。
もし、その項目がなければ、データの終わりまで検索を続けます。
したがって、線形探索は、配列の各要素を通過して、与えられた項目を見つけることができるアルゴリズムです。
線形探索では、要素を探索するための消費時間や比較回数が、アルゴリズムの効率性を判断するのに役立ちます。
検索する要素がデータ構造の最初の位置にある場合、必要な比較は1回だけです。
必要な要素が最後の位置にある場合、その要素を見つけるためにN回の比較が必要です。
ここで、Nはデータ項目の数を意味する。
バイナリサーチとは
バイナリサーチは高速なアルゴリズムです。
しかし、バイナリサーチを行う前に、データ項目をソートする必要がある。
バイナリサーチは、コレクション内の最も中央のアイテムを比較することで、アイテムを見つけます。
したがって、二項探索は、中間の要素を見つけ、その要素と探索する要素を比較するため、比較回数が少なく、より短い時間で探索することができます。
バイナリサーチでは、中間の要素が必要な要素であれば、そのインデックスが返されます。
中項目が検索された項目より上位であれば、検索された項目は中項目の左のサブアレイにある。
そうでなければ、中項目の右のサブアレイにある。
そして、この処理はサブアレイのサイズが0になるまで続けられる。
このアルゴリズムでは、探索するアイテムの数は毎回減少する。
Linear Search と Binary Search の違い
定義
線形探索は、リストの要素を順次チェックし、一致する要素を見つけるアルゴリズムです。
二項探索は、ソートされた配列の中から目的の値の位置を見つけるアルゴリズムです。
したがって、これが線形探索と二項探索の主な違いです。
同義語
順次探索は線形探索の別称であり、半周探索や対数探索は同じ二項探索のことである。
時間の複雑さ
線形探索の時間計算量は O(N) であるのに対し、二分探索の時間計算量は O(log2N) です。
この点も線形探索とバイナリサーチの違いと言える。
ベストケース
さらに、線形探索のベストケースは最初の位置にある要素を見つけることであり、バイナリサーチのベストケースは真ん中の位置にある要素を見つけることである。
配列の並べ替え
線形探索では、要素を探索する前に配列をソートする必要はありません。
しかし、バイナリサーチでは、要素を検索する前に、配列をソートする必要があります。
したがって、配列のソートの有無が線形探索とバイナリ探索の違いになります。
効率性
線形探索とバイナリサーチのもう一つの違いは、その効率性です。
バイナリサーチはリニアサーチより効率的です。
シンプルさ
また、バイナリサーチはリニアサーチよりも複雑です。
結論
配列のようなデータ構造中の要素を探索するアルゴリズムとして、線形探索と二項探索があります。
バイナリサーチは線形探索より効率的で高速ですが、探索操作を行う前にまず配列をソートすることが必須です。
このように、線形探索とバイナリサーチの主な違いは、線形探索と比較した場合、バイナリサーチはより効率的で、要素の探索にかかる時間が最短であることです。
