이진 검색으로 정렬된 두 배열의 중앙값 구하기

정렬된 두 배열이 주어졌을 때, 두 배열을 합친 전체 데이터의 중앙값(median)을 효율적으로 구하는 방법 중 하나가 이진 검색(Binary Search) 접근 방식입니다. 이 글에서는 C++로 해당 알고리즘을 직접 구현하는 과정을 단계별로 살펴보겠습니다.

핵심 아이디어

두 배열이 각각 정렬되어 있다는 특성을 활용하면, 각 배열의 개별 중앙값을 비교하는 것만으로도 전체 중앙값의 위치를 좁혀나갈 수 있습니다. 병합 정렬처럼 실제로 배열을 합치는 O(n+m) 방식과 달리, 이진 검색 기법은 탐색 범위를 절반씩 줄여 나가므로 O(log n)의 시간 복잡도를 달성할 수 있습니다.

알고리즘 동작 원리

중앙값 계산: 두 배열 각각의 시작 인덱스(s1, s2)와 끝 인덱스(e1, e2)를 받아, 각 배열의 중앙값 m1과 m2를 구합니다.
종료 조건 확인: 배열 길이가 1 또는 2인 경우에는 더 이상 분할하지 않고 남은 요소들만으로 최종 중앙값을 계산합니다.
중앙값 비교: m1과 m2가 같다면 그 값이 곧 전체 중앙값입니다.
탐색 범위 축소:
- m1 > m2라면, 전체 중앙값은 첫 번째 배열의 전반부 또는 두 번째 배열의 후반부에 존재합니다.
- m1 < m2라면, 전체 중앙값은 첫 번째 배열의 후반부 또는 두 번째 배열의 전반부에 존재합니다.
재귀 호출: 업데이트된 시작·끝 인덱스로 median() 함수를 재귀적으로 호출합니다.

C++ 예제 코드

#include<iostream>
using namespace std;

void median(float a1[], int s1, int e1, float a2[], int s2, int e2) {
    float m1, m2;
    // 현재 구간 길이가 짝수인 경우
    if((e1-s1+1)%2 == 0) {
        if(e1-s1 == 1) {  // 요소 2개만 남은 경우 종료 조건
            m1 = ((a1[s1]<a2[s2]?a1[s1]:a2[s2])+(a1[e1]>a2[e2]?a1[e1]:a2[e2]))/2;
            cout<<m1;
            return;
        }
        m1 = (a1[(e1+s1)/2]+a1[(e1+s1)/2+1])/2;  // 짝수 길이: 중앙 두 값의 평균
        m2 = (a2[(e2+s2)/2]+a2[(e2+s2)/2+1])/2;
        if(m1 == m2) {
            cout<<m1;
            return;
        }
        else {
            if(m1 > m2)
                median(a1, s1, (e1+s1)/2+1, a2, (e2+s2)/2, e2);
            else
                median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2+1);
        }
    }
    // 현재 구간 길이가 홀수인 경우
    else {
        if(e1-s1 == 0) {  // 요소 1개만 남은 경우 종료 조건
            m1 = (a1[s1]+a2[s2])/2;
            cout<<m1;
            return;
        }
        m1 = a1[(e1+s1)/2];  // 홀수 길이: 정중앙 값
        m2 = a2[(e2+s2)/2];
        if(m1 == m2) {
            cout<<m1;
            return;
        }
        else {
            if(m1 > m2)
                median(a1, s1, (e1+s1)/2, a2, (e2+s2)/2, e2);
            else
                median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2);
        }
    }
    return;
}

int main() {
    int n1, n2, i;
    cout<<"\nEnter the number of elements for 1st array: ";
    cin>>n1;
    float a1[n1];
    for(i = 0; i < n1; i++) {
        cout<<"Enter element for 1st array "<<i+1<<": ";
        cin>>a1[i];
    }
    cout<<"\nEnter the number of elements for 2nd array: ";
    cin>>n2;
    float a2[n2];
    for(i = 0; i < n2; i++) {
        cout<<"Enter element for 2nd array "<<i+1<<": ";
        cin>>a2[i];   // 참고: 두 번째 배열 입력은 a2에 저장되어야 합니다.
    }
    cout << "Median is ";
    median(a1, 0, n1-1, a2, 0, n2-1);
    return 0;
}

참고: 위 코드는 두 번째 배열 입력 시 값을 a1이 아닌 a2에 저장하도록 수정한 버전입니다. 원본 코드의 cin>>a1[i] 부분은 버그이며, 그대로 실행하면 두 번째 배열의 값들이 첫 번째 배열을 덮어쓰게 됩니다. 올바른 결과를 얻으려면 반드시 cin>>a2[i]로 수정해야 합니다.

실행 결과 예시

Enter the number of elements for 1st array: 5
Enter element for 1st array 1: 6
Enter element for 1st array 2: 7
Enter element for 1st array 3: 9
Enter element for 1st array 4: 10
Enter element for 1st array 5: 11
Enter the number of elements for 2nd array: 5
Enter element for 2nd array 1: 60
Enter element for 2nd array 2: 70
Enter element for 2nd array 3: 90
Enter element for 2nd array 4: 100
Enter element for 2nd array 5: 110
Median is 35

동작 검증

입력 예시를 통해 결과를 확인해 보겠습니다. 첫 번째 배열 {6, 7, 9, 10, 11}의 중앙값은 9이고, 두 번째 배열 {60, 70, 90, 100, 110}의 중앙값은 90입니다. m1(=9) < m2(=90)이므로, 전체 중앙값은 첫 번째 배열의 후반부 {9, 10, 11} 또는 두 번째 배열의 전반부 {60, 70, 90} 범위로 좁혀집니다. 재귀 호출을 거듭하다 보면 결국 두 배열의 경계 값들을 비교하여 최종 중앙값 35((10+60)/2 = 35)를 출력하게 됩니다.

시간 복잡도 분석

병합 방식: 두 배열을 하나로 합친 후 중앙값을 찾으면 O(n + m)의 시간이 소요됩니다.
이진 검색 방식: 매 재귀 호출마다 탐색 범위가 절반으로 줄어들므로 O(log n)으로 훨씬 효율적입니다. 대용량 데이터에서 특히 유리합니다.