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.

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

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;

}