4. Median of Two Sorted Arrays

• 겨우 풀기는 했는데 아직 upper bound를 구하는 부분을 명확하게 이해 못한거 같다.

• 기본적인 아이디어는 아래와 같다.
• 중간값을 포함하는 array의 절반에 해당하는 위치를 nums1, nums2에서 각각 찾는다.
• nums1의 중간값을 포함하는 upper bound pos1 를 설정한다
• nums1[pos1] 값을 기준으로 nums2 에서 upper bound 를 찾는다 = pos2
• 만일 pos1 + pos2 값이 중간값을 포함하는 위치 upperHalf 보다 작거나 크면 그에 맞출 수 있도록 pos1, pos2를 증가 또는 감소 시킨다.
• 이 때 증가는 두 위치의 값 중 작은 값을 가진 쪽, 감소는 두 위치의 값 중 큰 값을 가진 쪽에 대해서 수행한다.
• 중간값을 구한다.
• 전체 element의 수가 odd인 경우
• pos1, pos2는 각 array의 upper bound이므로 nums1[pos1 - 1], nums2[pos2 - 1] 값 중 큰 값을 중간값으로 한다.
• 전체 element의 수가 even인 경우
• upper bound는 두 개의 중간값 사이에 걸쳐 있다. 따라서 upper bound 이전의 값 하나와 upper bound 위치의 값을 평균내어 구한다.
• 두 array 모두 upper bound 이전에 element가 있는 경우
• ( max(nums1[pos1 - 1], nums2[pos2 - 1]) + min(nums1[pos1], nums2[pos2]) ) / 2
• nums1에만 upper bound 이전에 element가 있는 경우
• ( nums1[pos1 - 1] + min(nums1[pos1], nums2[pos2]) ) / 2
• nums2에만 upper bound 이전에 element가 있는 경우
• ( nums2[pos2 - 1] + min(nums1[pos1], nums2[pos2]) ) / 2

class Solution {
public:
    static constexpr int MIN_NUM = -1000000;
    static constexpr int MAX_NUM =  1000000;

    static inline int get(vector<int>& nums, int index, int defVal) {
        return index >= 0 && index < nums.size()
            ? nums[index] : defVal;
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int M = nums1.size(), N = nums2.size();
        bool even = (M + N) % 2 == 0;
        int upperHalf = (M + N + 1) / 2;
        int pos1 = (M + 1) / 2;
        auto itr = upper_bound(
            nums2.begin(), nums2.end(), 
            get(nums1, pos1, MAX_NUM + 1));
        int pos2 = itr - nums2.begin();
        while (pos1 + pos2 > upperHalf) {
            auto a = get(nums1, pos1 - 1, MIN_NUM - 1);
            auto b = get(nums2, pos2 - 1, MIN_NUM - 1);
            if (a > b) --pos1;
            else --pos2;
        }
        while (pos1 + pos2 < upperHalf) {
            auto a = get(nums1, pos1, MAX_NUM + 1);
            auto b = get(nums2, pos2, MAX_NUM + 1);
            if (a < b) ++pos1;
            else ++pos2;
        }
        if (even) {
            int a = 0, b = 0;
            if (pos1 > 0 && pos2 > 0) {
                a = max(
                    get(nums1, pos1 - 1, MIN_NUM - 1),
                    get(nums2, pos2 - 1, MIN_NUM - 1)
                );
                b = min(
                    get(nums1, pos1, MAX_NUM + 1),
                    get(nums2, pos2, MAX_NUM + 1)
                );
            } else if (pos1 > 0) {
                a = nums1[pos1 - 1];
                b = min(
                    get(nums2, 0, MAX_NUM + 1),
                    get(nums1, pos1, MAX_NUM + 1)
                );
            } else  {
                a = min(
                    get(nums1, 0, MAX_NUM + 1),
                    get(nums2, pos2, MAX_NUM + 1)
                );
                b = nums2[pos2 - 1];
            }
            return (a + b) / 2.0;
        } else {
            return max(
                get(nums1, pos1 - 1, MIN_NUM - 1),
                get(nums2, pos2 - 1, MIN_NUM - 1)
            );
        }
    }
};