推奨されます, 2024

エディターズチョイス

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

線形検索と二分検索は、要素を検索するために配列で使用される2つの方法です。 検索は、任意の順序で、またはランダムに格納されている要素の一覧から要素を見つけるプロセスです。

線形検索と二分検索の主な違いは、二分検索ではソートされた要素リストから要素を検索するのにかかる時間が短くなることです。 それで、二分探索法の効率は線形探索より大きいと推論した。

両者のもう一つの違いは、二分探索の前提条件があることです。つまり、線形探索ではそのような前提条件がないのに、要素はソートされなければなりません。 どちらの検索方法も、以下で説明するさまざまな手法を使用します。

比較表

比較基準線形検索二分検索
時間の複雑さに)O(log 2 N)
ベストケースタイム最初の要素O(1)中心要素O(1)
アレイの前提条件必要なし配列はソート順になっている必要があります
N個の要素に対する最悪の場合N回の比較が必要2 N回の比較のみをログに記録した後で終了できる
に実装することができます配列とリンクリストリンクリストに直接実装することはできません
挿入操作リストの最後に簡単に挿入ソートされたリストを維持するために適切な場所に挿入する処理を要求します。
アルゴリズムの種類本質的に反復分割して自然に征服する
使いやすさ使いやすく、注文された要素を必要としません。ともかく、扱いにくいアルゴリズムと要素は順番に整理されるべきです。
コード行もっと少なくもっと

線形検索の定義

線形検索では、配列の各要素が論理順に1つずつ検索され、目的の要素かどうかがチェックされます。 すべての要素にアクセスしても目的の要素が見つからない場合、検索は失敗します。 最悪の場合、配列サイズの半分(n / 2)をスキャンする必要がある平均的なケースの数。

したがって、線形検索は、指定された項目を見つけるために配列を順次横断する手法として定義できます。 以下のプログラムは、検索を使用した配列の要素の検索を示しています。

線形探索の効率

検索テーブル内のレコードを検索する際に行われる時間消費または比較の数によって、技法の効率が決まります。 目的のレコードが検索テーブルの最初の位置にある場合は、比較は1回だけ行われます。 目的のレコードが最後のレコードの場合、n回の比較が必要になります。 レコードが検索テーブル内のどこかに存在する場合、平均して、比較数は(n + 1/2)になります。 この技法の最悪の場合の効率はO(n)が実行順序を表すことです。

C線形探索法で要素を探索するためのプログラム

 #include #include void main(){int a [100]、n、i、item、loc = -1; clrscr(); printf( "\ n要素数を入力してください:"); scanf( "%d"、&n); printf( "数字を入力してください:\ n"); (i = 0; i <= n-1; i ++){scanf( "%d"、&a [i]); printf( "\ n検索する番号を入力してください:"); scanf( "%d"、&item); for(i = 0; i = 0){printf( "\ n%dが位置%d:に見つかりません。"、item、loc + 1); } else {printf( "\ n項目が存在しません"); getch(); } 

二分検索の定義

バイナリサーチは非常に効率的なアルゴリズムです。 この検索手法では、可能な限り最小限の比較で特定のアイテムを検索するのにかかる時間が短縮されます。 二分探索を行うには、まず、配列要素をソートする必要があります。

この手法の背後にある論理は以下のとおりです。

  • まず、配列の中央の要素を見つけます。
  • 配列の中央の要素は、検索対象の要素と比較されます。

3つのケースが発生する可能性があります。

  1. その要素が必須の要素であれば、検索は成功です。
  2. 要素が目的の項目より小さい場合は、配列の前半だけを検索します。
  3. それが目的の要素よりも大きい場合は、配列の後半部分を検索します。

要素が見つかるまで、または検索領域で使い果たされるまで、同じ手順を繰り返します。 このアルゴリズムでは、毎回検索領域が減少しています。 したがって、比較数は最大で対数(N + 1)です。 結果として、線形検索と比較すると効率的なアルゴリズムですが、バイナリ検索を実行する前に配列をソートする必要があります。

C二分探索法で要素を見つけるプログラム

 #include void main(){int i、beg、end、middle、n、検索、配列[100]; printf( "要素数を入力してください\ n"); scanf( "%d"、&n); printf( "%d番号を入力してください\ n"、n); (i = 0; i <n; i ++)の場合scanf( "%d"、&array [i]); printf( "検索する番号を入力してください\ n"); scanf( "%d"、&search); beg = 0; end = n - 1。 中央=(開始+終了)/ 2; while(beg <= end){if(array [middle] end)printf( "検索に失敗しました。%dがリストにありません。\ n"、検索); getch(); } 

線形検索と二分検索の主な違い

  1. 線形検索は本質的に反復的であり、順次アプローチを使用します。 一方、二分探索は分割統治法を実行します。
  2. 線形探索の時間複雑度はO(N)であり、二分探索はO(log 2 N)です。
  3. 線形探索における最良の場合の時間は最初の要素、すなわちO(1)に対するものです。 反対に、二分探索では、それは真中の要素、すなわちO(1)に対するものです。
  4. 線形探索において、要素を探索するための最悪の場合はN回の比較である。 対照的に、それは二分探索のための比較のlog 2 N数です。
  5. 線形検索はリンクリストだけでなく配列でも実行できますが、バイナリ検索はリンクリストで直接実行することはできません。
  6. 私たちが知っているように、バイナリサーチはその理由でソートされた配列を必要とします。 それどころか、線形検索はソートされた要素を必要としないので、要素はリストの最後に簡単に挿入されます。
  7. 線形検索は使いやすく、順序付けされた要素は必要ありません。 一方、2分探索アルゴリズムは注意が必要で、要素は必ず順番に並べられます。

結論

用途に応じて、線形および二分探索アルゴリズムの両方が有用であり得る。 配列がデータ構造であり、要素がソートされた順序で配置されている場合は、2分検索がクイック検索に適しています。 要素がどのように配置されているかにかかわらず、リンクリストがデータ構造である場合、バイナリ検索アルゴリズムの直接実装が利用できないため、線形検索が採用されます。

リンクリストは本質的に動的であり、中間要素が実際にどこに割り当てられているのかがわからないため、通常のバイナリ検索アルゴリズムはリンクリストには使用できません。 したがって、バイナリ検索の方が線形検索より実行が速いため、リンクリストでも機能するバイナリ検索アルゴリズムのバリエーションを設計する必要があります。

Top