Question

Give an O(log m + log n)-time algorithm that takes two sorted lists of sizes m and n, respectively, as input and returns the ith smallest element in the union of the two lists. Justify your algorithm and analyze its running time.

Answer 1

Binary search is used similarly. K'th element is found in more productive way.

Explanation:

arr1 and arr2 are the middle elements which are compared, let us compute as mid1 and mid2. Let us predict arr1 [mid1] k, the elements are not needed after mid2 elements.  arr2 are set as last element for arr2 [mid2].  New sub problems are defined. When one array is half the size.

C++ code for the algorithm.

#include <iostream>

using namespace std;    

int kth(int *arr1, int *arr2, int *end1, int *end2, int k)

{

if (arr1 == end1)

return arr2[k];

if (arr2 == end2)

return arr1[k];

int mid1 = (end1 - arr1) / 2;

int mid2 = (end2 - arr2) / 2;

if (mid1 + mid2 < k)

{

if (arr1[mid1] > arr2[mid2])

return kth(arr1, arr2 + mid2 + 1, end1, end2,

k - mid2 - 1);

else

return kth(arr1 + mid1 + 1, arr2, end1, end2,

k - mid1 - 1);

}

else

{

if (arr1[mid1] > arr2[mid2])

return kth(arr1, arr2, arr1 + mid1, end2, k);

else

return kth(arr1, arr2, end1, arr2 + mid2, k);

}    

int main()

{

int arr1[5] = {2, 3, 6, 7, 9};

int arr2[4] = {1, 4, 8, 10};    

int k = 5;

cout << kth(arr1, arr2, arr1 + 5, arr2 + 4, k - 1);

return 0;

}