试图理解这个算法从两个排序的数组中找到Kth min

Question

描述:
给定两个排序的数组(非下降),在T = O(lg(m + n))中找到Kth min元素,m和n分别是两个数组的长度.

问题:
不了解下面的算法大约有三点:

• 当A [aPartitionIndex] <B [bPartitionIndex]时,为什么我们可以直接丢弃A的左边部分？
• 为什么不能同时丢弃A的左侧部分和B的右侧部分？
• 一些"资源"说这个算法可以应用于在N个排序数组中找到Kth min,怎么样？将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)你永远不能放弃数组的正确部分,因为你不知道它们在排序中的位置.