Question

I need to find the kth smallest element in the union of 2 sorted arrays in O(log |A| + log |B|) time. I understand this is similar to binary search, but I don't understand which parts of the arrays I can throw out at each level of recursion, and why. In the pseudocode below, what should go into $1 through $16 and why?

// A and B are each sorted into ascending order, and 0 <= k < |A|+|B|
// Returns the element that would be stored at index k if A and B were
// combined into a single array that was sorted into ascending order.
select (A, B, k)
    return select(A, 0, |A|-1, B, 0, |B|-1, k)

select(A, loA, hiA, B, loB, hiB, k)
    // A[loA..hiA] is empty
    if (hiA < loA)
        return B[k-loA]
    // B[loB..hiB] is empty
    if (hiB < loB)
        return A[k-loB]
    // Get the midpoints of A[loA..hiA] and B[loB..hiB]
    i = (loA+hiA)/2
    j = (loB+hiB)/2
    // Figure out which one of four cases apply
    if (A[i] > B[j])
        if (k <= i+j)
            return select(A, $1, $2, B, $3, $4, k);
        else
            return select(A, $5, $6, B, $7, $8, k);         
    else
        if (k <= i+j)
            return select(A, $9, $10, B, $11, $12, k);
        else
            return select(A, $13, $14, B, $15, $16, k);

Answer 1

$1 = Alo,$2 = i,$3, = Blo,$4 = Bhi

$5 = Alo,$6 = Ahi,$7 = j,$8 = Bhi

$9 = Alo,$10 = Ahi,$11 = Blo,$12 = j

$13 = i,$14 = Ahi,$15 = Blo,$16 = Bhi

Explanation:

This is a divide and conquer algorithm. There is a minor improvement in the algorithm which can be made by dividing both the arrays in k/2 instead of their respective mid-points.

The motivation of the algorithm is that we want to find some index I in A and J in B such that I + J = k, in this case max(A[I], B[J]) is the kth smallest element.

I will explain to you the pseudo code by going through the important parts line by line.

1. select (A, B, k)
return select(A, 0, |A|-1, B, 0, |B|-1, k)

This line is the initial call to our recursive function so Alo = 0 and Ahi = |A|-1.

2.if (hiA < loA)
        return B[k-loA]
    if (hiB < loB)
        return A[k-loB]

In these lines, if while comparing we reach the end of an array we just return the required element from the other array.

3.i = (loA+hiA)/2
    j = (loB+hiB)/2
    // Figure out which one of four cases apply
    if (A[i] > B[j])
        if (k <= i+j)
            return select(A, $1, $2, B, $3, $4, k);
        else
            return select(A, $5, $6, B, $7, $8, k);         
    else
        if (k <= i+j)
            return select(A, $9, $10, B, $11, $12, k);
        else
            return select(A, $13, $14, B, $15, $16, k);

This is the most important step in recursion. To get a better understanding to think of this recursive step as trimming the two arrays to achieve the above result.

If the mid element of a is greater than mid element of b

• If mid-index of a + mid-index of b is less than k
  • we can ignore the first half of b
• else we can safely ignore the second half of a

If mid element of a is less than mid element of b

• If mid-index of a + mid-index of b is less than k
  • ignore the first half of a, adjust k.else ignore the first half of a
• else we can ignore the second half of b.