[javascript] 검색 알고리즘

18 Dec 2023

javascript

검색 알고리즘이란 데이터 또는 정보에서 특정한 항목을 찾는 데 사용되는 방법이며, 효율적인 검색 알고리즘은 많은 분야에서 중요한 역할을 합니다. 이 글에서는 선형 검색과 이진 검색 두 가지 기본적인 검색 알고리즘에 대해 알아보고자 합니다.

1. 선형 검색

선형 검색은 리스트에서 원하는 항목을 찾을 때, 처음부터 끝까지 차례대로 비교하는 방법을 사용합니다. 이 알고리즘은 간단하고 직관적이지만, 리스트가 크고 원하는 항목이 끝에 있는 경우에는 효율이 떨어질 수 있습니다.

function linearSearch(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) {
            return i;  // 찾은 경우 해당 인덱스 반환
        }
    }
    return -1;  // 못 찾은 경우 -1 반환
}

2. 이진 검색

이진 검색은 리스트가 정렬된 상태에서 중간 값과 비교하여 찾고자 하는 항목이 왼쪽 또는 오른쪽에 위치한지를 판단하여 탐색 범위를 반으로 줄여가며 검색하는 방법입니다. 이 알고리즘은 선형 검색보다 빠르며, 리스트 크기가 큰 경우 효과적으로 사용될 수 있습니다.

function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (array[mid] === target) {
            return mid;  // 찾은 경우 해당 인덱스 반환
        } else if (array[mid] < target) {
            left = mid + 1;  // 왼쪽 범위를 좁힘
        } else {
            right = mid - 1;  // 오른쪽 범위를 좁힘
        }
    }
    return -1;  // 못 찾은 경우 -1 반환
}

요약

선형 검색은 간단하지만 큰 리스트에서는 효율적이지 않을 수 있으며, 이진 검색은 정렬된 리스트에서 빠르게 원하는 항목을 찾을 수 있는 방법입니다. 검색 알고리즘은 데이터 구조와 함께 고려하여 적절하게 선택해야 합니다.

이렇게 검색 알고리즘은 데이터 처리에서 매우 중요한 역할을 하며, 알맞은 알고리즘을 선택하여 효율적으로 원하는 정보를 찾는 데 도움이 됩니다.

참고 문헌: