JS 자료구조 & 알고리즘 - 검색 알고리즘

검색 알고리즘

• 선형 검색
• 이진 검색
• KMP 문자열 검색 알고리즘

선형 검색

가장 간단한 검색 방법

• 모든 요소를 순회하면서 내가 원하는 값인지 확인하는 것
• 이 방법도 데이터 분류 상태에 따라 나쁜 방법은 아니다.

JS의 선형 검색 내장 함수

• indexOf, find, includes, findIndex

간단한 선형 검색 알고리즘

• 문제

  배열과, 숫자를 받는 함수를 작성한다.

  숫자 값이 배열안에 존재하는 경우, 함수는 해당 숫자의 index를 반환하고

  배열안에 숫자값이 없을 경우 -1을 반환한다.

• 작성함수

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

선형 검색의 빅오

• O(n)
• 배열의 수가 길어질수록 시간복잡도 또한 비례적으로 증가한다.

이진 검색 알고리즘

• 이진 검색은 분류된 데이터를 대상으로만 작동하므로 데이터가 잘 분류된 상태여야만 한다.
• 하나씩 확인하여 후보군에서 지우는 것이 아닌, 원하는 값이 아님을 확인했을 때, 해당 섹션의 전체 요소를 부정하는 개념
• 선형검색보다 훨씬 빠르다.

이진검색 알고리즘 예제

• 문제

  정렬된 배열과 값을 받아들이고 값이 존재하는 경우 그 인덱스를 반환하는 binarySearch라는 함수를 작성합니다. 값이 존재하지 않으면 -1을 반환합니다.

• 코드

    function binarySearch(arr, val) {
        // 시작, 중간, 끝 initialize
        let start = 0;
        let end = arr.length - 1;
        let middle = Math.floor((start + end) / 2);
          
      
        while(arr[middle] !== val && start <= end) { // start가 end보다 커지거나, end가 start보다 작아지면 loop 종료
            // pick 값이 val 보다 크면 end 를 middle - 1로 당겨온다.
            if(arr[middle] > val) end = middle - 1;
            // pick 값이 val 보다 작으면 start 를 middle + 1로 밀어놓는다.
            else start = middle + 1;
            // 다시 평균 중간점 구하기
            middle = Math.floor((start + end) / 2);
            console.log(start, end, middle)
        }
      
        return arr[middle] === val ? middle : -1;
    }
      
    binarySearch([
      5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
      40, 44, 64, 79, 84, 86, 95, 96, 98, 99
    ], 10) // 2
  

이진 검색 알고리즘의 빅오

• 최악의 경우 : O(log n)
• 최선의 경우 : O(1) - 중간 값으로 뽑은 값이 찾고자 하는 값일 수 있다.

나이브 문자열 검색

제공된 문자열에서, 일종의 문자열 패턴이 얼마나 등장하는지에 대해 찾는 알고리즘

• 예제

    function naiveSearch(long, short) {
        let count = 0;
        for (let i = 0; i< long.length; i++) {
            for (let j = 0; j < short.length; j++) {
                if(short[j] !== long[i + j]) {
                    break;
                }
                if (j === short.length - 1) count++;
            }
        }
        return count;
    }
      
    naiveSearch("lorie loled", "lol") // 1