線形検索とバイナリ検索の違い

著者: Laura McKinney
作成日: 1 4月 2021
更新日: 13 5月 2024
Anonim
離散数学-3.1.2検索アルゴリズム
ビデオ: 離散数学-3.1.2検索アルゴリズム

コンテンツ


線形検索とバイナリ検索は、配列で使用される2つの方法です。 探している 要素。検索とは、任意の順序で、またはランダムに保存された要素のリスト内の要素を見つけるプロセスです。

線形検索とバイナリ検索の主な違いは、バイナリ検索では要素のソートされたリストから要素を検索する時間が短くなることです。したがって、バイナリ検索法の効率は線形検索よりも大きいと推測されます。

2つの違いは、バイナリ検索の前提条件があることです。つまり、要素は ソート済み 線形検索では、そのような前提条件はありません。どちらの検索方法も、以下で説明する異なる手法を使用しています。

  1. 比較表
  2. 定義
  3. 主な違い
  4. 結論

比較表

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


線形検索の定義

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

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

効率 線形探索の

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

Cプログラム 線形検索手法で要素を検索します。

＃含める ＃含める void main（）{int a、n、i、item、loc = -1; clrscr（）; f（ " n要素の数を入力してください："）; scanf（ "％d"、＆n）; f（ "数字を入力してください： n"）; for（i = 0; i <= n-1; i ++）{scanf（ "％d"、＆a）; } f（ " n検索する番号を入力してください："）; scanf（ "％d"、＆item）; for（i = 0; i <= n-1; i ++）{if（item == a）{loc = i;ブレーク; }} if（loc> = 0）{f（ " n％dは％dの位置にあります："、item、loc + 1）; } else {f（ " nアイテムが存在しません"）; } getch（）; }

バイナリ検索の定義

バイナリ検索は非常に効率的なアルゴリズムです。この検索手法は、可能な限り最小限の比較で特定のアイテムを検索する時間を短縮します。バイナリ検索を行うには、まず配列要素を並べ替える必要があります。


この手法の背後にあるロジックを以下に示します。

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

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

  1. 要素が必須要素である場合、検索は成功します。
  2. 要素が目的のアイテムより小さい場合、配列の前半のみを検索します。
  3. 目的の要素よりも大きい場合は、配列の後半を検索します。

検索領域で要素が見つかるかなくなるまで、同じ手順を繰り返します。このアルゴリズムでは、検索エリアが縮小するたびに。したがって、比較の数は最大でlog（N + 1）です。結果として、線形検索と比較すると効率的なアルゴリズムですが、バイナリ検索を実行する前に配列をソートする必要があります。

Cプログラム バイナリ検索手法で要素を見つける。

＃含める void main（）{int i、beg、end、middle、n、search、array; f（ "要素の数を入力してください n"）; scanf（ "％d"、＆n）; f（ "％dの数字を入力してください n"、n）; for（i = 0; i <n; i ++）scanf（ "％d"、＆array）; f（ "検索する番号を入力してください n"）; scanf（ "％d"、＆search）; beg = 0; end = n-1; middle =（beg + end）/ 2; while（beg <= end）{if（array <search）beg = middle + 1; else if（array == search）{f（ "検索は成功しました。 n％dは％d。 nの場所で見つかりました。"、search、middle + 1）;ブレーク; } else end = middle-1; middle =（beg + end）/ 2; }（beg> end）f（ "検索に失敗しました！リストに％dが存在しません。 n"、検索）; getch（）; }

  1. 線形検索は本質的に反復的であり、順次アプローチを使用します。一方、バイナリ検索は分割統治アプローチを実装しています。
  2. 線形検索の時間の複雑さはO（N）であり、バイナリ検索にはO（log2N）。
  3. 線形検索の最適なケースは、最初の要素、つまりO（1）です。反対に、バイナリ検索では、中間要素、つまりO（1）が対象です。
  4. 線形検索では、要素を検索する最悪のケースはN回の比較です。対照的に、それはログです2バイナリ検索のN個の比較。
  5. 線形検索は配列とリンクリストに実装できますが、バイナリ検索はリンクリストに直接実装できません。
  6. バイナリ検索にはソートされた配列が必要であることがわかっているため、適切な場所に挿入してソートされたリストを維持する処理が必要です。それどころか、線形検索はソートされた要素を必要としないため、要素はリストの最後に簡単に挿入されます。
  7. 線形検索は使いやすく、順序付けられた要素は必要ありません。一方、バイナリ検索アルゴリズムは注意が必要であり、要素は必ず順序どおりに配置されます。

結論

アプリケーションによっては、線形検索アルゴリズムとバイナリ検索アルゴリズムの両方が役立つ場合があります。配列がデータ構造であり、要素がソートされた順序で配置されている場合、バイナリ検索が優先されます 速い検索。リンクリストが要素の配置方法に関係なくデータ構造である場合、バイナリ検索アルゴリズムの直接実装が利用できないため、線形検索が採用されます。

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