Search code examples
javaarraysalgorithmbig-odivide-and-conquer

Trying to understand this algorithm for finding Kth min from two sorted array


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.

Question:
Do not understand the algorithm below about three points:

  • Why we can drop the left part of A directly, when A[aPartitionIndex] < B[bPartitionIndex]?
  • Why can not drop the left part of A, and the right part of B at the same time?
  • Some "resource" said this algorithm can be applied on finding Kth min in N sorted arrays, how? split k into N parts?

Code: Java. Solution: Binary Search.

    // 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);
        }
    }

Solution

  • 1) Assuming that A and B are sorted in ascending order, A[aPartitionIndex] < B[bPartitionIndex] implies that A[i] < B[bPartitionIndex] for all i < aPartitionIndex.

    2) You can never drop the right part of an array because you don't know where they fit in the ordering.