Search Algorithm

5190 ワード
アルゴリズム#アルゴリズム# テキストリンク

1️⃣ Search Algorithm ?


Search Algorithmはその名の通り探す方法です.配列が指定され、検索する値がある場合は、検索する値が指定された配列に存在するかどうかを確認します.JSのArrayオブジェクトにはSearchメソッドが内蔵されている.indexOf、include、find、findIndexなど.

2▼▼リニアサーチ?

  • の配列と入力値を受け入れます.
  • アレイを参照して、現在の要素と値が同じかどうかを確認します.
    • 与えられた値に一致する要素がある場合はtrue、indexなどを返します.与えられた値に一致する要素が存在しない場合はfalseまたは-1などを返します. 
           function linearSearch(array, num) {
         for (let i = 0; i < array.length; i++) {
             if (array[i] === num) return i;
         }
           return -1;
         }
    線形検索は上記のとおりです.すべての要素を巡回して値を探します.従ってO(N)時間複雑度を持つ.(上記のArrayオブジェクトのメソッドはこれに該当します)

    3バイナリ検索?


    バイナリ検索は、前の線形検索よりもずっと速い検索方法です.要素を値と比較した後、サイズ比較の結果、残りの要素の半分を取り除くことができます.(バイナリ検索はソートされた配列でしか使用できません)簡単に理解すると、Up&Downゲームをプレイすることも考えられます.
  • 並べ替えの並べ替えと値を入力します.
  • 配列の先頭に左ポインタを作成し、配列の末尾に右ポインタを作成します.
  • 左ポインタが右ポインタ以下になるまで、次の操作を行います.
    3-1中間ポインタの作成
    3-2の中間ポインタが値と一致する場合、indexまたはtrueが返されます.
    3-3中間ポインタの値が検索値より小さい場合、検索する値は中間ポインタの右側に存在します.
    3-4中間ポインタの値が検索値より小さい場合、検索する値は中間ポインタの右側、
    • にあります.
  • の値が見つからない場合は、-1またはfalseを返します.
    • function binarySearch(array, num) {
 let left = 0;
 let right = array.length - 1;

 while (left <= right) {
  let mid = Math.floor((left + right) / 2);
  if (arr[mid] === num) return num;
  if (arr[mid] < num) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

return -1;
}
    ホットペッパーAPIからレストラン検索するサンプル
    ジャバスクリプト — 避けるべきこと