C/C++로 구현하는 크기가 같은 정렬된 두 배열의 중앙값 찾기

이 글에서는 크기가 같은 두 개의 정렬된 배열에서 중앙값(median)을 구하는 방법을 알아봅니다. 배열 요소는 C++ STL의 vector를 사용해 저장하며, 두 배열을 하나로 병합한 후 중앙값을 계산합니다.

크기가 같은 두 배열을 병합하면 최종 배열의 요소 개수는 항상 짝수가 됩니다. 따라서 가운데 위치한 두 개의 요소를 선택하고, 이들의 평균값을 중앙값으로 반환하면 됩니다.

알고리즘

median(arr1, arr2)

Begin
    arr3 := arr1과 arr2를 병합한 배열
    arr3 정렬
    len := arr3의 길이
    mid := len / 2
    median := (arr3[mid] + arr3[mid-1]) / 2
    return median
End

예제 코드

아래 코드에서는 STL의 merge() 함수로 두 배열을 병합한 뒤, sort()로 정렬하여 중앙값을 계산합니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

float median(vector<int> arr1, vector<int> arr2) {
    vector arr3(arr1.size() + arr2.size());
    merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
    sort(arr3.begin(), arr3.end());
    int len = arr3.size();
    int mid = len / 2;
    return float(arr3[mid] + arr3[mid-1]) / 2;
}

main() {
    vector<int> arr1 = {1, 3, 4, 6, 7};
    vector<int> arr2 = {4, 5, 7, 8, 9};
    cout << "Median: " << median(arr1, arr2);
}

출력 결과

Median: 5.5

위 예제에서 첫 번째 배열 {1, 3, 4, 6, 7}과 두 번째 배열 {4, 5, 7, 8, 9}을 병합·정렬하면 총 10개의 요소를 가진 배열이 만들어집니다. 이 배열의 가운데 두 요소는 5와 6이며, 두 값의 평균인 5.5가 최종 중앙값이 됩니다.