지난 포스트에서는 JavaScript에서 가장 일반적인 몇 가지를 살펴보았습니다. 이제 검색 알고리즘에 대해 이야기하고 싶습니다. 예를 들어 에 있는 게시물과 같은 다른 게시물을 확인했다면 DEV에서 검색 알고리즘에 대해 쓴 것이 이번이 처음이 아님을 알 수 있습니다. 즉, 이 기사에서는 가장 일반적인 검색 알고리즘 중 일부를 자세히 살펴보고 실제로 분석하는 것을 목표로 합니다. 이 기사에서는 다음 검색 알고리즘을 다룰 것입니다.

선형 검색(순차 검색이라고도 함)

이진 검색

보간 검색

선형 검색

순차 검색이라고도 하는 선형 검색은 가장 기본적인 검색 알고리즘입니다. O(n)의 a를 사용하면 선형 검색은 데이터 구조의 각 요소를 검색 중인 요소와 비교하는 것으로 구성됩니다. 값을 찾았는지 여부에 따라 찾고 있던 값을 반환할지 또는 부울을 반환할지 여부는 구현에 달려 있습니다. 짐작할 수 있듯이 이것은 매우 비효율적인 프로세스입니다.

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

이진 검색

이진 검색 알고리즘은 정렬된 데이터 구조와 함께 작동합니다. 이 구현에서는 퀵 정렬 알고리즘을 사용합니다. 이 알고리즘의 big-O 표기법은 O(log n)입니다. 프로세스는 다음과 같습니다.

(정렬된) 배열

중간에 있는 value를 선택합니다.

value가 검색 ​​대상이면 완료된 것입니다

.

그렇지 않고 검색하는 항목이 value보다 작으면 왼쪽 하위 배열

을 사용하여 1단계로 돌아갑니다.

또는 찾고자 하는 것이 value 보다 크면 올바른 하위 배열을 사용하여 1단계로 돌아가십시오.

function binarySearch(arr, target) {
    const sortedArr = quickSort(arr);
    let low = 0;
    let high = sortedArr.length - 1;
    while (low <= high) {
        const mid = Math.floor(low + high);
        const element = sortedArr[mid];
        if (element < target) {
            low = mid + 1;
        } else if (element > target) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return null;
}

보간 검색

보간 검색은 기본적으로 이진 검색의 향상된 버전입니다. 이 검색 알고리즘은 전화번호부에서 이름을 검색하는 방법과 유사합니다. 각 단계에서 알고리즘은 나머지 검색 공간에서 대상 요소가 대상 요소와 비교한 경계 값을 기반으로 할 수 있는 위치를 계산합니다. 요소가 균일하게 분포된 경우 시간 복잡도는 O(log(log n))입니다. 최악의 경우 O(n)까지 소요될 수 있습니다.

이 알고리즘의 단계는 첫 번째 단계를 제외하고 이진 검색의 단계와 동일합니다. 배열 중간에 있는 값을 value로 선택하는 대신 아래 구현에서 알 수 있는 position 공식을 사용하여 값을 선택합니다.

function interpolationSearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    let position = -1;
    let delta = -1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        delta = (target - arr[low])/(arr[high] - arr[low]);
        position = low + Math.floor((high - low) * delta);
        if (arr[position] === target) {
            return position;
        }
        if (arr[position] < target) {
            low = position + 1;
        } else {
            high = position - 1;
        }
    }
    return null;
}

다음 예에서는 분포가 매우 균일하고 델타/차이가 매우 작기 때문에 이 검색에 매우 이상적인 상황입니다.

결론

이 기사가 몇 가지 일반적인 검색 알고리즘을 더 명확하게 이해하는 데 도움이 되었기를 바랍니다. 검색 알고리즘은 알고리즘 연습의 기본이며 훨씬 더 복잡하고 흥미로운 솔루션에 대한 문을 열어줍니다. 이 게시물에서 다루는 많은 자료에 의존하는 향후 게시물에서 몇 가지 흥미로운 알고리즘을 검토할 예정이니 계속 지켜봐 주시기 바랍니다.