C++로 정렬된 두 배열의 중앙값 구하기: 이진 탐색 기반 풀이

두 개의 정렬된 배열이 주어졌을 때, 이 두 배열 전체의 중앙값(median)을 찾는 문제입니다. 예를 들어 배열이 [1, 5, 8]과 [2, 3, 6, 9]라면, 두 배열을 합쳤을 때 [1, 2, 3, 5, 6, 8, 9]가 되고 총 원소 개수는 7개(홀수)이므로 정답은 가운데 값인 5가 됩니다.

이 문제는 두 배열을 실제로 병합하지 않고도 이진 탐색(binary search)을 활용하면 O(log(min(m, n))) 시간 복잡도로 효율적으로 해결할 수 있습니다.

해결 접근 방식

핵심 아이디어는 작은 배열을 기준으로 분할 지점(partition)을 이진 탐색으로 찾아, 두 배열을 왼쪽 부분과 오른쪽 부분으로 나누었을 때 다음 조건이 만족되는 지점을 찾는 것입니다.

왼쪽 부분의 최댓값이 오른쪽 부분의 최솟값보다 작거나 같다

구체적인 알고리즘 단계는 다음과 같습니다.

함수 findMedianSortedArrays를 정의하고, nums1과 nums2 배열을 인자로 받습니다.
만약 nums1의 크기가 nums2보다 크다면, 인자 순서를 바꿔 재귀 호출합니다. 즉, findMedianSortedArrays(nums2, nums1)을 반환합니다. (항상 더 작은 배열을 기준으로 탐색하기 위함)
x := nums1의 크기, y := nums2의 크기로 설정합니다.
low := 0, high := x로 초기화합니다.
totalLength := x + y로 설정합니다.
low <= high인 동안 반복합니다.
- partitionX := low + (high - low) / 2
- partitionY := (totalLength + 1) / 2 - partitionX
- maxLeftX = partitionX가 0이면 -무한대, 그렇지 않으면 nums1[partitionX - 1]
- minRightX = partitionX가 x이면 +무한대, 그렇지 않으면 nums1[partitionX]
- maxLeftY = partitionY가 0이면 -무한대, 그렇지 않으면 nums2[partitionY - 1]
- minRightY = partitionY가 y이면 +무한대, 그렇지 않으면 nums2[partitionY]
- 만약 maxLeftX <= minRightY이고 maxLeftY <= minRightX라면 올바른 분할 지점을 찾은 것이므로:
  - totalLength가 짝수라면 → (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2를 반환합니다.
  - 홀수라면 → max(maxLeftX, maxLeftY)를 반환합니다.
- 그렇지 않고 maxLeftX > minRightY라면 → high := partitionX - 1로 조정합니다.
- 그 외의 경우 → low := partitionX + 1로 조정합니다.
반복문이 종료되면 0을 반환합니다.

C++ 구현 예제

다음 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size())
            return findMedianSortedArrays(nums2, nums1);
        int x = nums1.size();
        int y = nums2.size();
        int low = 0;
        int high = x;
        int totalLength = x + y;
        while(low <= high){
            int partitionX = low + (high - low) / 2;
            int partitionY = (totalLength + 1) / 2 - partitionX;
            int maxLeftX = (partitionX == 0 ? INT_MIN : nums1[partitionX - 1]);
            int minRightX = (partitionX == x ? INT_MAX : nums1[partitionX]);
            int maxLeftY = (partitionY == 0 ? INT_MIN : nums2[partitionY - 1]);
            int minRightY = (partitionY == y ? INT_MAX : nums2[partitionY]);
            if(maxLeftX <= minRightY && maxLeftY <= minRightX){
                if(totalLength % 2 == 0){
                    return ((double)max(maxLeftX, maxLeftY) + (double)min(minRightX, minRightY)) / 2;
                } else {
                    return max(maxLeftX, maxLeftY);
                }
            }
            else if(maxLeftX > minRightY)
                high = partitionX - 1;
            else
                low = partitionX + 1;
        }
        return 0;
    }
};
int main(){
    Solution ob;
    vector<int> v1 = {1, 5, 8}, v2 = {2, 3, 6, 9};
    cout << ob.findMedianSortedArrays(v1, v2);
}

입력

[1,5,8]
[2,3,6,9]

출력

시간 및 공간 복잡도

시간 복잡도: O(log(min(m, n))) — 더 작은 배열에 대해서만 이진 탐색을 수행하므로 매우 효율적입니다.
공간 복잡도: O(1) — 추가적인 배열 저장 없이 상수 개의 변수만 사용합니다.

이 방법은 두 배열을 하나씩 병합하며 중앙값을 찾는 O(m + n) 방식보다 훨씬 빠르며, 특히 배열의 크기가 클 때 그 차이가 두드러집니다.