JavaScript 이진 탐색(Binary Search) 구현: 배열에서 숫자의 인덱스 찾기

이번 글에서는 정렬된 숫자 배열과 검색하려는 숫자를 각각 첫 번째, 두 번째 인자로 받는 JavaScript 함수를 작성해 보겠습니다.

함수의 동작 방식은 다음과 같습니다.

• 검색하는 숫자가 배열에 존재하면 → 해당 요소의 인덱스를 반환
• 존재하지 않으면 → -1을 반환

이진 탐색(Binary Search)이란?

이 문제는 이진 탐색 알고리즘을 활용해 해결해야 합니다. 이진 탐색은 대표적인 분할 정복(Divide and Conquer) 알고리즘으로, 배열을 반복적으로 절반씩 나누어가며 탐색 범위를 좁혀 결국 하나의 요소에 도달할 때까지 진행합니다.

이진 탐색에서 배열이 반드시 정렬되어 있어야 하는 이유는 명확합니다. 배열이 정렬되어 있으면 중간값과 목표 값을 비교했을 때, 찾고자 하는 값이 어느 쪽 절반에 있는지 쉽게 판단할 수 있기 때문입니다.

구현 예제

const arr = [-3, -1, 4, 7, 9, 11, 14, 22, 26, 28, 36, 45, 67, 78, 88, 99];
const binarySearch = (arr = [], num) => {
    let l = 0;
    let r = arr.length - 1;
    while(l <= r){
        const mid = Math.floor((l + r) / 2);
        if(num == arr[mid]){
            return mid;
        }
        else if(num < arr[mid]){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        };
    };
    return -1
};
console.log(binarySearch(arr, 22));
console.log(binarySearch(arr, 56));
console.log(binarySearch(arr, 11));

동작 원리 살펴보기

위 코드의 핵심 로직은 다음과 같습니다.

1. 탐색 범위 초기화: 왼쪽 포인터(l)는 0, 오른쪽 포인터(r)는 배열의 마지막 인덱스로 설정합니다.
2. 중간값 계산: (l + r) / 2를 내림하여 중간 인덱스 mid를 구합니다.
3. 비교 후 범위 축소:
   • 목표 값이 중간값과 같으면 → mid를 반환
   • 목표 값이 중간값보다 작으면 → 오른쪽 포인터를 mid - 1로 이동 (왼쪽 절반 탐색)
   • 목표 값이 중간값보다 크면 → 왼쪽 포인터를 mid + 1로 이동 (오른쪽 절반 탐색)
4. 탐색 실패 처리: l > r이 되어 반복문이 종료되면 값을 찾지 못한 것이므로 -1을 반환합니다.

실행 결과

콘솔 출력 결과는 다음과 같습니다.

7
-1
5

22는 인덱스 7에 위치하고, 56은 배열에 존재하지 않아 -1이 반환되며, 11은 인덱스 5에 있음을 확인할 수 있습니다.

마무리

이진 탐색은 선형 탐색(O(n))과 달리 시간 복잡도가 O(log n)으로 매우 효율적입니다. 데이터 양이 많아질수록 그 성능 차이가 극명해지므로, 정렬된 배열에서 특정 값을 빠르게 찾아야 할 때 이진 탐색을 적극적으로 활용해 보시기 바랍니다.