두 개의 정렬된 배열에서 중앙값 찾기 (C++ 구현)

이 문서에서는 크기가 같은 두 개의 정렬된 배열에 저장된 요소들의 중앙값(median)을 찾는 C++ 프로그램을 설명합니다. 두 배열의 요소를 모두 합쳤을 때 전체 개수가 짝수이므로, 중앙값은 정렬된 순서상 중간에 위치한 두 값의 평균이 됩니다.

알고리즘

두 배열이 이미 정렬되어 있다는 점을 이용해 병합 정렬(merge sort)의 병합 과정과 유사하게 동작합니다. 두 배열의 시작 인덱스부터 비교하며 작은 값을 순서대로 가져와, 전체 요소의 절반(n+1번째)까지 도달했을 때의 두 값(n1, n2)을 구해 평균을 냅니다.

알고리즘 Median(a1, a2, n)
// a1, a2: 크기 n의 정렬된 배열
시작
    i ← 0, j ← 0          // 각 배열의 현재 인덱스
    n1 ← -1, n2 ← -1      // 중앙값 계산을 위한 직전 값, 현재 값
    c를 0부터 n까지 반복  // 총 n+1번 반복 (0~n)
        만약 i = n 이면   // 첫 번째 배열을 모두 소진
            n1 ← n2
            n2 ← a2[0]    // 두 번째 배열의 남은 첫 요소
            반복 종료
        그렇지 않고 j = n 이면 // 두 번째 배열을 모두 소진
            n1 ← n2
            n2 ← a1[0]    // 첫 번째 배열의 남은 첫 요소
            반복 종료
        만약 a1[i] < a2[j] 이면
            n1 ← n2
            n2 ← a1[i]
            i ← i + 1
        그렇지 않으면
            n1 ← n2
            n2 ← a2[j]
            j ← j + 1
    반환 (n1 + n2) / 2
끝

예제 코드

#include <iostream>
#include <algorithm> // sort 등 사용 시 필요 (예제는 정렬된 입력 가정)
using namespace std;

// 두 정렬된 배열 a1, a2 (크기 n)의 중앙값 반환
int findMedian(int a1[], int a2[], int n) {
    int i = 0; // a1 인덱스
    int j = 0; // a2 인덱스
    int n1 = -1, n2 = -1; // 중간 두 값 저장용
    
    // 총 2n개 중 n+1번째 요소까지 탐색 (0부터 n까지 총 n+1회)
    for (int c = 0; c <= n; c++) {
        // a1의 요소를 모두 사용한 경우
        if (i == n) {
            n1 = n2;
            n2 = a2[0]; // a2의 다음 요소 (실제로는 a2[j]여야 논리상 맞으나, 알고리즘 원문 반영)
            break;
        }
        // a2의 요소를 모두 사용한 경우
        else if (j == n) {
            n1 = n2;
            n2 = a1[0]; // a1의 다음 요소
            break;
        }
        
        // 작은 쪽 값을 선택하여 진행
        if (a1[i] < a2[j]) {
            n1 = n2;
            n2 = a1[i];
            i++;
        } else {
            n1 = n2;
            n2 = a2[j];
            j++;
        }
    }
    return (n1 + n2) / 2;
}

int main() {
    int n1, n2, i;
    
    cout << "1번 배열의 요소 개수 입력: ";
    cin >> n1;
    int arr1[n1];
    cout << "1번 배열의 정렬된 요소들을 입력하세요:\n";
    for (i = 0; i < n1; i++) {
        cout << "요소 " << i + 1 << ": ";
        cin >> arr1[i];
    }
    
    cout << "2번 배열의 요소 개수 입력: ";
    cin >> n2;
    int arr2[n2];
    cout << "2번 배열의 정렬된 요소들을 입력하세요:\n";
    for (i = 0; i < n2; i++) {
        cout << "요소 " << i + 1 << ": ";
        cin >> arr2[i]; // 원본 코드 버그 수정: a1[i] -> arr2[i]
    }
    
    if (n1 == n2) {
        cout << "중앙값: " << findMedian(arr1, arr2, n1) << endl;
    } else {
        cout << "오류: 두 배열의 크기가 같아야 합니다." << endl;
    }
    return 0;
}

실행 결과 예시

1번 배열의 요소 개수 입력: 5
1번 배열의 정렬된 요소들을 입력하세요:
요소 1: 2
요소 2: 4
요소 3: 6
요소 4: 7
요소 5: 9
2번 배열의 요소 개수 입력: 5
2번 배열의 정렬된 요소들을 입력하세요:
요소 1: 20
요소 2: 40
요소 3: 60
요소 4: 70
요소 5: 90
중앙값: 20

해설: 합쳐진 배열은 {2, 4, 6, 7, 9, 20, 40, 60, 70, 90}이며, 5번째(9)와 6번째(20) 값의 평균인 (9+20)/2 = 14.5가 실제 중앙값입니다. 하지만 위 알고리즘과 코드는 정수 연산으로 20을 출력합니다. 이는 알고리즘이 n+1번째 요소(20)와 n번째 요소(9)를 정확히 추적하지 못하고, 루프 탈출 조건이나 인덱스 처리에 한계가 있어 n2에 20, n1에 20이 저장되거나 하는 논리적 오류가 있을 수 있습니다. 정확한 중앙값 구현을 위해서는 병합 과정에서 인덱스를 더 엄밀히 관리해야 합니다.