[JSアルゴリズム]探索アルゴリズム(線形探索、バイナリ探索、Naive String Search)


せんけいたんさく

  • 検索方法
  • 所与の配列で値を検索する가장 간단한 방법配列内のすべての要素を表示し、必要な値であるかどうかを確認する.
  • javascriptには배열に対する様々な検索方法がある.
  • indexOf
  • includes
  • find
  • findIndex
  • これらの関数はどのように動作しますか?
  • 全て後から全てのエレメントをチェックし、入力があるか確認する.これが線形検索です.
  • nが大きくなり、配列の長さも長くなり、時間も長くなります.次のコードはBigO(n)値を持つ線形探索である.
  • function linearSearch(arr, val) {
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] === val) return i;
      }
      return -1;
    }
    
    console.log(linearSearch([34, 56, 1, 2], 1));
  • リニアサーチBigOの性能
  • Best : O(1)
  • Worst : O(n)
  • Average : O(n)
  • リニアサーチは、データがソートされていない場合に最適です.
  • バイナリサーチ

  • バイナリサーチ比リニアサーチ훨씬 빠르다
  • リニアサーチは1回ずつ削除するのとは異なり、バイナリサーチでは中間点を繰り返し捉え、残りの要素で条件を満たさない절반을 제거次に、残りの部分について同じ手順を繰り返します.
  • ただしバイナリプローブは使用不可정렬된 배열
  • Divide and Conquer方式.
  • バイナリ検索コード
  •     - 이 함수는 정렬된 배열과 검색할 값을 인수로 받는다.
          - 배열의 시작 부분에 왼쪽 포인터를 만들고 배열의 끝 부분에 오른쪽 포인터를 만들고, 중간 포인터도 만든다.
          - 검색한 값과 중앙 포인터의 값이 같지 않으며서 왼쪽 포인터가 오른쪽 포인터 앞에 오는 동안:
            - 값이 크면 오른쪽 포인터를 중앙 포인터의 왼쪽으로 이동
            - 값이 작으면 왼쪽 포인터를 중앙 포인터의 오른쪽으로 이동
            - 좌우 포인터의 중간 인덱스로 중앙 포인터를 재설정
        	- 검색한 값과 중앙 포인터 값이 같은 경우, 해당 중앙 포인터 반환하고 이외에는 -1 반환
  • While重複文を用いたバイナリ検索コード
  •     function binarySearch(arr, elem) {
          var start = 0;
          var end = arr.length - 1;
          var middle = Math.floor((start + end) / 2);
          while (arr[middle] !== elem && start <= end) {
            if (elem < arr[middle]) end = middle - 1;
            else start = middle + 1;
            middle = Math.floor((start + end) / 2);
          }
          return arr[middle] === elem ? middle : -1;
        }
        
        console.log(
          binarySearch(
            ['apple', 'banana', 'cola', 'dexter', 'eft', 'finder', 'google'],
            'google'
          )
        );
  • バイナリ検索の性能:非常に良い(ソートにのみ適用される配列)
  • Worst and Average Case : O(log2nlog_2nlog2​n)
  • Best Case : O(1)
  • 32要素からバイナリ検索を行う場合は、log 232 log 232 log 232 32値の5ステップを経ることができる.
  • nの大きさが2倍になるごとに1段階増える
  • Naive String Search

  • 最もよく使われる問題の解き方
  • 長い文字列の中で何回短い文字列が現れるか数えたい場合、
  • 1文字しか確認されていない場合、最も直感的な方法は、すべての文字を順番に確認(線形検索)することです.
  • ただし、パターン(2文字以上)を特定するには、以下のNavive String Searchメソッドを使用します.
  • Native String Searchコード
  •     -문자열(긴 문자열, 찾는 패턴)을 받는 함수를 정의한다.
        - 긴 문자열 루프를 돈다.
        	- 짧은 문자열(찾는 패턴) 루프를 돈다.
        		- 만약 문자가 일치하지 않으면, 내부 루프에서 벗어난다.
        		- 문자가 일치하면 계속 진행한다.
        	- 내부 루프(짧은문자열 루프)를 완료하고 일치하는 항목을 찾으면 일치 횟수를 증가시킨다.
  • Native String Searchコード
  •     function naiveStringSearch(long, short) {
          let count = 0;
          for (let i = 0; i < long.length; i++) {
            for (let j = 0; j < short.length; j++) {
              if (long[i + j] !== short[j]) break;
              if (j === short.length - 1) count++;
            }
          }
          return count;
        }
        
        console.log(naiveStringSearch('wowomgzomg', 'omg')); // 2