Leetcode 4 : Median of Two Sorted Arrays

Leetcode 4 : Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 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)).

analysis:

M1: find the median of two sorted arrays: as for sorted arrays, we can use mergesort to linear finding the median element, time complexity is O(n)
M2: as the requested complexity is O(log n), we can use binary search to solve this problem
we can first solve find the kth smallest element in two sorted array, then apply k to (array1.size() + array2.size()) / 2;
How to find the kth smallest element in two sorted array?
step1: compare the k/2th element in two array,
           if array1[k/2] is smaller than array2[k/2], then the kth smallest element is not
           in the first k/2 elements in array1; otherwise, the kth smallest element is not
           in the first k/2 elements in array2. In this way, we can remove half k elements
           in one of the array.
step2: In the rest of arrays, we have to find k-k/2 th element, because we have
           remove the smallest k/2 elements in the two array;
step3: do a recursion of step1 and step2, when the base case fits, we can find the
           kth smallest element.
 int findkth(vector<int> nums1, int left1, int left2,vector<int> nums2, int k) {
        //base case
        if (left1 >= nums1.size()) return nums2[left2 + k -1];
        if (left2 >= nums2.size()) return nums1[left1 + k -1];
        if (k == 1) { //find the first smallest element
            return min(nums1[left1], nums2[left2]);
        }
        int half_1 = left1 + k/2 -1 < nums1.size()? nums1[left1 + k/2-1] : INT_MAX;
        int half_2 = left2 + k/2 -1 < nums2.size()? nums2[left2 + k/2-1] : INT_MAX;
        if (half_1 < half_2) {
            return findkth(nums1, left1 + k/2, left2, nums2, k - k/2);
        }else {
            return findkth(nums1, left1, left2 + k/2, nums2, k - k/2);
        }
    }

After finding the kth smallest element in two sorted array, we can  give k = array1.size() + array2.size(), if k is odd, then we can find the middle one with k/2-1, if k is even , we have to find the k/2th smallest element also, then compute the average number of k/2-1 th and k/2 th element.
Time complexity : O(log(m+n))