중앙값 찾는 문제

gistfile1.txt

/*
https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

Q: There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

사고흐름: 이미 정렬됨, O(log(m+n)) hint 주어짐. -> 바이너리 서치 또는 merge소트 병합단계를 활용해야할듯?-> 바이너리 서치로는 안풀림 -> 머지소트 병합단계를 활용하면? -> 이미정렬되어있으므로 O(m+n)에는 가능.

O(log(m+n))에 어떻게 찾을 수 있을까?

*/
class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int temp[m+n];
        int leftIt = 0;
        int rightIt = 0;
        int cnt = 0;
         
        while(leftIt<m && rightIt<n) {
            if(A[leftIt] < B[rightIt]) {
                temp[cnt++] = A[leftIt++];
            } else {
                temp[cnt++] = B[rightIt++];
            }
        }
         
        while(leftIt<m) temp[cnt++] = A[leftIt++];
        while(rightIt<n) temp[cnt++] = B[rightIt++];
         
        if((m+n) % 2 == 1 ) {
            return temp[(m+n)/2];
        } else {
            return ((double)(temp[(m+n)/2] + temp[(m+n)/2-1])/2);
        }
    }
};

위 솔루션은 간단히 O(m+n)입니다. O(log(m+n))으로 어떻게 step을 전개해 나갈 수 있을까요?

일단 저도 비슷하게 풀었는데요. 일단 찾기만 하면 되니까 A, B 포인터만 움직이고 별도의 temp 배열을 필요없을 것 같아요. 그런데 O(log(m+n)) 찾는게 어렵군요. ㅜ.ㅜ

이 문제 한번 생각날때 끝까지 풀어봐야겠습니다. 일단 광성님 풀이 붙여넣습니다.

두 번째는 제가 거꾸로 설명했습니다. -_- 방향이 반대로 되었다고 생각하시면 됩니다.
A= { 1, 2, 3, 4, 5, 6, 7}, B= {1,2,3, 10} 이라고 합시다.
mA = 4, mB = 2.5 입니다.
mA > mB 이므로 mB의 우측 값의 일부 혹은 전체 (여기서는 3) 이 mA의 왼쪽에 포함될 수 있습니다.
따라서 전체의 중간값은 mA의 좌측과 mB의 우측에만 존재할 수 있습니다.
따라서 mA의 우측(5, 6, 7), mB의 좌측(1, 2) 를 버릴 수 있을텐데, 좌측에서 2개, 우측에서 3개를 버려버리면 미디언 값 찾는 과정이 틀어지기 때문에
좌측에서 2개, 우측에서 2개씩만 버릴 수 있습니다.
따라서 O(log(N+M)) 이 될 수는 없을 것 같습니다.