Question

You are given two arrays A1 and A2, each with n elements sorted in increasing order. For simplicity, you may assume that the keys are all distinct from each other. Describe an o(log n) time algorithm to find the (n/2) th smallest of the 2n keys assuming that n is even.

Answer 1

using namespace std;

  

int kth(int arr1[], int arr2[], int m, int n, int k)

{

    int sorted1[m + n];

    int i = 0, j = 0, d = 0;

    while (i < m && j < n)

    {

        if (arr1[i] < arr2[j])

            sorted1[d++] = arr1[i++];

        else

            sorted1[d++] = arr2[j++];

    }

    while (i < m)

        sorted1[d++] = arr1[i++];

    while (j < n)

        sorted1[d++] = arr2[j++];

    return sorted1[k - 1];

}

  

int main()

{

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

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

    int k = 5;

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

    return 0;

}