JavaScript로 정렬된 2차원 배열에서 이진 탐색하기

이 글에서는 숫자로 이루어진 2차원 배열과 하나의 숫자를 인수로 받아, 해당 숫자가 배열 안에 존재하는지 판별하는 JavaScript 함수를 작성해 보겠습니다.

여기서 다루는 2차원 배열은 다음과 같은 조건을 만족합니다.

각 하위 배열(행)은 오름차순으로 정렬되어 있습니다.
앞선 하위 배열의 어떤 원소도 뒤따르는 하위 배열의 어떤 원소보다 크지 않습니다. 즉, 모든 행을 한 줄로 펼치면 완전히 정렬된 형태가 됩니다.

함수는 이진 탐색(binary search) 알고리즘을 활용해 두 번째 인수로 전달된 값을 검색해야 하며, 값이 존재하면 true, 존재하지 않으면 false를 반환합니다.

입력 및 출력 예시

예를 들어 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [
    [2, 6, 9, 11],
    [13, 16, 18, 19, 21],
    [24, 26, 28, 31]
];
const num = 21;

이 경우 함수는 다음과 같은 결과를 반환해야 합니다.

true

접근 방식

이 문제는 두 단계로 나누어 효율적으로 해결할 수 있습니다.

대상 행 찾기: 각 행의 첫 번째 원소와 마지막 원소를 비교하여, 목표값이 그 범위 안에 속하는 행을 찾습니다.
이진 탐색 수행: 찾아낸 행 안에서 이진 탐색을 실행해 목표값이 실제로 존재하는지 확인합니다.

이 방식을 사용하면 불필요한 행까지 탐색하지 않으므로 탐색 범위를 크게 줄일 수 있습니다.

구현 코드

const arr = [
    [2, 6, 9, 11],
    [13, 16, 18, 19, 21],
    [24, 26, 28, 31]
];
const num = 21;

const search2D = (array = [], target) => {
    const h = array.length;
    const w = h > 0 ? array[0].length : 0;

    // 빈 배열인 경우 바로 false 반환
    if (h === 0 || w === 0) { return false; }

    // 목표값이 포함될 가능성이 있는 행 찾기
    const arr = getArr();
    if (!arr) { return false; }

    // 해당 행에서 이진 탐색 실행
    return binarySearch(arr, target) !== null;

    function getArr() {
        for (let i = 0; i < h; i++) {
            let arr = array[i];
            if (arr[0] <= target && target <= arr[arr.length - 1]) {
                return arr;
            }
        }
        return null;
    }

    function binarySearch(arr, t) {
        let left = 0;
        let right = arr.length - 1;
        while (left <= right) {
            if (arr[left] === t) {
                return left;
            }
            if (arr[right] === t) {
                return right;
            }
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] === t) {
                return mid;
            }
            if (arr[mid] < t) {
                left = mid + 1;
            }
            else if (arr[mid] > t) {
                right = mid - 1;
            }
        }
        return null;
    }
};

console.log(search2D(arr, num))

실행 결과

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

true

동작 방식 정리

getArr() 함수는 각 행의 시작 값과 끝 값을 목표값과 비교하여 후보 행을 선별합니다. 목표값이 어느 행의 범위에도 속하지 않으면 즉시 false를 반환하므로, 존재하지 않는 값에 대한 탐색도 빠르게 종료됩니다.

binarySearch() 함수는 선택된 행에서 좌우 경계를 좁혀 가며 탐색을 진행합니다. 매 반복마다 양 끝 값과 중간 값을 함께 확인해 탐색 속도를 높였으며, 값을 찾으면 해당 인덱스를, 찾지 못하면 null을 반환합니다.

행의 개수를 m, 한 행의 길이를 n이라 할 때, 이 구현의 시간 복잡도는 O(m + log n)입니다. 행을 선별하는 데 최대 m번의 비교가 필요하고, 이후 이진 탐색에는 log n번의 비교만 필요하기 때문입니다.