Median of Two Sorted Array

Question

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)).

Solution

照九章的教法，如果要從 linear complexity 再優化，應該要先想到 log complexity，而這個條件也是剛好題目所要。一想到 log complexity，如果是 O(nlogn)，得想到：

1. 排序
2. 使用 logn 的數據結構再乘以個數 (n)

若只是單純的 log，那可以往二分法去思考。這題的思路可以往一個廣義一點的做法去想，從找 Median 升格到找第 k 位。既然要找第 k 位，再加上要套入二分法，想到的就是去比較兩個 array 的 k/2 個位置誰大誰小。因為在把兩個小 array merge 起來時，倘若 A[k/2] < B[k/2]，代表 A array 前 k/2 個數放到大 array 時，其實第 k 位還沒出現。因此可以捨棄 A array 的前 k/2 個數 （誰 k/2 位的數字小，誰就被捨棄），再找 k - k/2 位，如此遞迴去做

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;       
        if (len % 2 == 1) {
            return findKth(nums1, 0, nums2, 0, len / 2 + 1);
        } else {
            return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
        }
    }

    public static int findKth(int[] nums1, int nums1_start, int[] nums2, int nums2_start, int k) {
        if (nums1_start >= nums1.length) {
            return nums2[nums2_start + k - 1];
        } else if (nums2_start >= nums2.length) {
            return nums1[nums1_start + k - 1];
        }

        if (k == 1) {
            return Math.min(nums1[nums1_start], nums2[nums2_start]);
        }

        int nums1_key = nums1_start + k / 2 - 1 < nums1.length?nums1[nums1_start + k / 2 - 1]:Integer.MAX_VALUE;
        int nums2_key = nums2_start + k / 2 - 1 < nums2.length?nums2[nums2_start + k / 2 - 1]:Integer.MAX_VALUE;

        if (nums1_key < nums2_key) {
            return findKth(nums1, nums1_start + k / 2, nums2, nums2_start, k - k / 2);
        } else {
            return findKth(nums1, nums1_start, nums2, nums2_start + k / 2, k - k / 2);
        }
    }