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

ロジックとデータ構造の基本概念を導入する単純なアルゴリズムがいくつかありますが、より複雑さを目的としたアルゴリズムもあります。

検索アルゴリズムは、電話帳内の連絡先やコンピューター上のファイルを見つけるなど、大量のデータ内の情報を見つけるのに役立ちます。

この意味で、この記事は線形探索アルゴリズムと二分探索アルゴリズムに関連する概念を紹介することを目的としています。

1.線形探索

• リストを順番にスキャンして要素を見つけます
• 配列内の特定の数値を検索する例です

線形検索アルゴリズムは、説明文では、整数の配列と、入力パラメーターとなるターゲットと呼ばれる検索の参照となる値を持つことを意味します。この意味で、これらの値を受け取る関数があり、まずこの配列の各位置を既存の位置の最大サイズまで調べます。これには主に for を使用します。次に、if を使用して、各位置がターゲットと等しい値を持つかどうかのチェックが条件となります。値が見つかった場合、関数はその位置のインデックスを返すか、見つからない場合を表す -1 を返します。

JavaScript を使用した例は次のようになります。

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

したがって、このアルゴリズムは、要素が配置されている位置またはインデックスを返すことを目的としており、さらには、最初に対応する要素を見つけてから続行する必要なく、単にその要素を見つけることさえも目的としています。この動作はアルゴリズムの命令によって発生します。アルゴリズムは、条件が満たされると要素インデックスを使用して return を実行し、その後ループを抜けて関数を終了します。

このアルゴリズムは、小さいリストや順序付けされていないリストが存在するシナリオで役立ちます。各要素を走査する必要があり、余分なメモリ使用量はありません。

2.二分探索

• 順序付きリストをスクロールして要素を見つけます
• 配列内の特定の数値を検索する例があります

二分探索アルゴリズムは、ソートされた配列内で指定された値を見つけるためのより効率的な形式のアルゴリズムです。これは、検索範囲を繰り返し半分に分割することで機能するため、大規模なデータセットの線形検索よりも大幅に高速になります。二分探索の複雑さは O(log n) ですが、線形探索は O(n) です。

JavaScript の例としては次のとおりです。

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

ロジックは 2 つのポインターから始まり、1 つは配列の先頭 (ロー) に、もう 1 つは配列の末尾 (ハイ) にあります。したがって、中間インデックスは const middle = Math.floor((low high) / 2) として計算されます。これにより、各ステップで中間要素がターゲットと比較されます。中間要素がターゲットと等しい場合、インデックスが返されます。ただし、中央の要素がターゲットより小さい場合、または中央 より大きい場合は、このプロセスは、ターゲットが見つかるまで、または範囲が無効になるまで繰り返されます (low > の場合)。高い。

二分検索は、アルファベット順の辞書や順序付けされた日付のセットなど、順序付けされたデータを見つける場合に効率的です。各反復で問題をより小さなサブ問題に分割できるため、より高速かつ効率的になる傾向があります。

したがって、線形探索は単純であり、小さなリストに対して機能することがわかります。二分探索ははるかに効率的ですが、順序付けられたデータが必要です。

さまざまなアルゴリズムがどのように機能するか、およびその使用状況を理解することは、効率的な計算ソリューションを構築するための重要なステップです。これらの方法を実装して分析してみて、現実世界の課題を解決するためにこれらの戦略をどのように適用できるかを発見してください。 =)

以上がアルゴリズム: 線形探索と二分探索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。