JavaScript의 일반적인 검색 알고리즘

저는 현재 몇 주 동안 코딩 후 부트캠프에 있으며 기술 인터뷰의 세계를 탐색하기 시작했습니다. 이를 통해 데이터 구조 및 알고리즘에 대한 심층 분석이 필요합니다. 교수법을 학습 도구로 사용하는 것에 관심을 갖고 여기에서 학습 과정을 문서화할 것입니다.

검색 알고리즘부터 시작하겠습니다!

선형 검색

선형 검색은 배열과 값을 받아들이고 해당 값이 존재하는 인덱스를 반환하는 일반적인 검색 알고리즘입니다. 해당 값이 없으면 함수는 -1을 반환합니다. 구현:

i에서 시작하여 배열 길이를 반복하는 for 루프로 시작합니다

.

현재 배열 요소가 주어진 값과 같은지 확인하십시오.

찾은 경우 해당 값의 인덱스를 반환합니다

.

값이 없으면 -1을 반환합니다.
코드는 다음과 같습니다.

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

이 함수의 평균 및 최악의 시간 복잡도는 O(N)이고 최상의 시간 복잡도는 O(1)입니다. 우리의 다음 검색 알고리즘은 이 시간 복잡성을 개선할 것입니다.

이진 검색

이진 검색은 정렬된 배열에서만 작동한다는 경고와 함께 선형 검색보다 훨씬 효율적일 수 있는 알고리즘입니다. 구현:

정렬된 배열과 값을 받는 함수를 만듭니다.

배열 시작 부분에 왼쪽 포인터를 만들고 배열 끝에 오른쪽 포인터를 만듭니다.

왼쪽 포인터가 오른쪽 포인터 앞에 있는 경우:

배열 중간에 포인터를 만듭니다. 시작 및 끝 값의 평균을 구하고 Math.floor()를 사용하여 반올림된 숫자

를 확인하여 이 중간 값을 찾을 수 있습니다.

일치하는 값을 찾으면 인덱스를 반환합니다

.

값이 너무 작은 경우 왼쪽 포인터를 위로 이동합니다

.

값이 너무 크면 오른쪽 포인터를 아래로 이동합니다

.

올바른 값을 찾을 때까지 이 프로세스를 계속합니다

.

값이 없으면 -1을 반환합니다

.

코드는 다음과 같습니다.

function binarySearch(arr, elem) {
    let start = 0;
    let end = arr.length - 1;
    let 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;
}

기억하다! 이 방법은 정렬된 배열에서만 작동합니다! 그러나 정렬된 배열이 있는 경우 선형 검색과 비교할 때 시간 복잡도가 크게 향상됩니다. 최악의 평균 시간 복잡도는 O(log n)이고 최상의 경우는 O(1)입니다.

순진한 문자열 검색

내가 다룰 최종 검색 알고리즘은 순진한 문자열 검색입니다. 이 알고리즘은 더 큰 문자열 내에서 패턴을 찾는 데 유용합니다. 예를 들어 문자열 "AABAACAADAABAABA"에 "AABA"가 몇 번이나 나타나는지 찾을 수 있습니다. 구현:

더 큰 문자열을 취한 다음 찾고 있는 패턴이 포함된 문자열을 취하는 함수를 정의합니다

.

더 긴 문자열을 반복합니다

.

해당 루프 내에서 짧은/패턴 문자열을 반복합니다

.

일치 확인

일치하는 항목을 찾으면 계속 진행합니다

.

완전히 일치하는 항목을 찾으면 일치 항목 수를 늘리십시오

.

일치하는 항목이 없으면 내부 루프에서 나갑니다

.

마지막에 총 개수 반환

코드는 다음과 같습니다.

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;
}

순진한 문자열 검색을 위한 최상의 시간 복잡도는 O(n)입니다. 최악의 경우는 O(m*(n-m+1))입니다. This author에서는 이 고유한 시간 복잡도에 대해 자세히 설명합니다.

이것은 JavaScript의 기본 검색 알고리즘에 대한 빠른 가이드였습니다. 나는 여전히 이 자료를 배우고 있으며 의견과 비평을 환영합니다!

출처

자세한 내용은 현재 수강 중인 Udemy 과정을 확인하세요! JavaScript Algorithms and Data Structures Masterclass

The Naive String Matching Algorithm

Naive Algorithm for Pattern Searching