java - 试图理解这个从两个排序数组中找到第 K 个最小值的算法

Question

Description:
Given two sorted arrays (none-descending), find the Kth min element in T = O(lg(m + n)), m and n are length of two arrays, respectively.

问题:
不理解以下三点算法:

• 当 A[aPartitionIndex] < B[bPartitionIndex] 时，为什么我们可以直接删除 A 的左边部分？
• 为什么不能丢弃 A 的左边部分，而 B 的右边部分在同一时间？
• 一些“资源”说这个算法可以用于寻找第 K 个最小值在 N 个排序数组中，如何？将 k 分成 N 部分？

代码:Java。 解决方案:二分查找。

    // k is based on 1, not 0.
    public int findKthMin(int[] A, int as, int ae, 
                           int[] B, int bs, int be, int k) {

        int aLen = ae - as + 1;
        int bLen = be - bs + 1;

        // Guarantee the first array's size is smaller than the second one,
        // which is convenient to remaining part calculation.
        if (aLen > bLen) return findKthMin(B, bs, be, 
                                           A, as, ae, k);

        // Base case.
        if (aLen == 0) return B[bs + k - 1];
        if (k == 1) return Math.min(A[as], B[bs]); // k based on 1, not 0.

        // Split k, 
        // one part is distributed to A,
        // the other part is distributed to B.
        int ak = aLen < (k/2)? aLen: k/2;
        int bk = k - ak;

        // *k is based on 1, not 0.
        int aPartitionIndex = as + (ak - 1);
        int bPartitionIndex = bs + (bk - 1);

        if (A[aPartitionIndex] == B[bPartitionIndex]) {
            return A[aPartitionIndex];

        } else if (A[aPartitionIndex] < B[bPartitionIndex]) {
            // Drop the left part of A, and
            // do recursion on the right part of A, and
            // the entire current part of B.
            k = k - ak;
            return findKthMin(A, aPartitionIndex + 1, ae, 
                              B, bs, be, k);

        } else {
            // Drop the left part of B, and
            // do recursion on the entire current part of A, and
            // the right part of B.
            k = k - bk;
            return findKthMin(A, as, ae, 
                              B, bPartitionIndex + 1, be, k);
        }
    }

Answer 1

1) 假设A和 B按升序排列，A[aPartitionIndex] < B[bPartitionIndex]暗示 A[i] < B[bPartitionIndex]对于所有 i < aPartitionIndex .

2) 你永远不能删除数组的正确部分，因为你不知道它们在排序中的位置。