两个有序数组中第k小的数

给定两个升序数组a和b，且两个数组的交集为空，a的数组长度为m，b的数组长度为n，求两个升序数组的全局第k小的数。(m >> k,n >> k)

public class Solution {
    public static int findKthElement(int[] a, int[] b, int k) {
        int m = a.length;
        int n = b.length;
        return findKth(a, 0, m, b, 0, n, k);
    }

    // 辅助函数，递归寻找两个数组的第 k 小元素
    private static int findKth(int[] a, int aStart, int m, int[] b, int bStart, int n, int k) {
        // aStart和bStart都在递增，k在递减，所以都需要越界检查。
        // 如果数组 a 已经空了，直接返回数组 b 中的第 k 小的数
        if (aStart >= m) {
            return b[bStart + k - 1];
        }
        // 如果数组 b 已经空了，直接返回数组 a 中的第 k 小的数
        if (bStart >= n) {
            return a[aStart + k - 1];
        }
        // 如果 k == 1，返回两个数组当前最小的元素
        if (k == 1) {
            return Math.min(a[aStart], b[bStart]);
        }

        // 计算两个数组的第 k/2 个元素，注意越界检查。就是说，如果索引越界，aMid就取最大值。
        int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
        if (aStart + k / 2 - 1 < m) {
            // [aStart, aStart + k / 2 - 1]中正好k/2个元素。因为数组是有序的，所以a[aStart + k / 2 - 1]是这k/2个元素中的最大值
            aMid = a[aStart + k / 2 - 1];
        }
        if (bStart + k / 2 - 1 < n) {
            bMid = b[bStart + k / 2 - 1];
        }

        // 如果 aMid 小于 bMid，说明 a 中的前 k/2 个元素不可能包含第 k 小的元素。重点。
        if (aMid < bMid) {
            return findKth(a, aStart + k / 2, m, b, bStart, n, k - k / 2);
        } else {
            // 如果 bMid 小于等于 aMid，说明 b 中的前 k/2 个元素不可能包含第 k 小的元素
            return findKth(a, aStart, m, b, bStart + k / 2, n, k - k / 2);
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 7, 10, 15};
        int[] b = {2, 5, 8, 12, 14};
        int k = 5;
        System.out.println("第 " + k + " 小的元素是: " + findKthElement(a, b, k));  // 结果应该是 7
    }
}

• 时间复杂度：$O(\log(m + n))$。
• 空间复杂度：$O(\log(m + n))$。