Alex Rivera | Logout

How to find the kth smallest element in the union of two sorted arrays?

Asked 2011-01-05T18:43:59.717
117

This is a homework question, binary search has already been introduced:

Given two arrays, respectively N and M elements in ascending order, not necessarily unique:
What is a time efficient algorithm to find the kth smallest element in the union of both arrays?

They say it takes O(logN + logM) where N and M are the arrays lengths.

Let's name the arrays a and b. Obviously we can ignore all a[i] and b[i] where i > k.
First let's compare a[k/2] and b[k/2]. Let b[k/2] > a[k/2]. Therefore we can discard also all b[i], where i > k/2.

Now we have all a[i], where i < k and all b[i], where i < k/2 to find the answer.

What is the next step?

arrays algorithm binary-search divide-and-conquer
Edit
Report

1 Answer

5

Here's a C++ iterative version of @lambdapilgrim's solution (see the explanation of the algorithm there):

#include <cassert>
#include <iterator>

template<class RandomAccessIterator, class Compare>
typename std::iterator_traits<RandomAccessIterator>::value_type
nsmallest_iter(RandomAccessIterator firsta, RandomAccessIterator lasta,
               RandomAccessIterator firstb, RandomAccessIterator lastb,
               size_t n,
               Compare less) {
  assert(issorted(firsta, lasta, less) && issorted(firstb, lastb, less));
  for ( ; ; ) {
    assert(n < static_cast<size_t>((lasta - firsta) + (lastb - firstb)));
    if (firsta == lasta) return *(firstb + n);
    if (firstb == lastb) return *(firsta + n);

    size_t mida = (lasta - firsta) / 2;
    size_t midb = (lastb - firstb) / 2;
    if ((mida + midb) < n) {
      if (less(*(firstb + midb), *(firsta + mida))) {
        firstb += (midb + 1);
        n -= (midb + 1);
      }
      else {
        firsta += (mida + 1);
        n -= (mida + 1);
      }
    }
    else {
      if (less(*(firstb + midb), *(firsta + mida)))
        lasta = (firsta + mida);
      else
        lastb = (firstb + midb);
    }
  }
}

It works for all 0 <= n < (size(a) + size(b)) indexes and has O(log(size(a)) + log(size(b))) complexity.

Example

#include <functional> // greater<>
#include <iostream>

#define SIZE(a) (sizeof(a) / sizeof(*a))

int main() {
  int a[] = {5,4,3};
  int b[] = {2,1,0};
  int k = 1; // find minimum value, the 1st smallest value in a,b

  int i = k - 1; // convert to zero-based indexing
  int v = nsmallest_iter(a, a + SIZE(a), b, b + SIZE(b),
                         SIZE(a)
answered 2012-07-28T05:51:25.230

Your Answer