In: Computer Science
Divide and conquer problem.
Suppose we are given two sorted arrays A[1 . . . n] and B[1 . .
. n] and an integer k. Describe an algorithm to find the kth
smallest element in the union of A and B in O(log n) time. For
example, if k = 1, your algorithm should return the smallest
element of A ∪ B; if k = n, your algorithm should return the median
of A ∪ B.)
You can assume that the arrays contain no duplicate elements using
divide and conquer.
(b) Now suppose we are given three sorted arrays A[1 . . . n], B[1
. . . n], and C[1 . . . n], and an integer k. Describe an algorithm
to find the kth smallest element in A ∪ B ∪ C in O(log n) time
using divide and conquer (not heap)
Solution:
Code: O(log n) solution
#include <bits/stdc++.h>
using namespace std;
int kSmallest(int A[], int B[], int *endA, int *endB, int k)
{
// if array A is empty, then return kth value in B
if(A==endA)
return B[k];
// if array B is empty, then return kth value in A
if(B==endB)
return A[k];
// Find mid index of array A and B
int midA = (endA - A)/2;
int midB = (endB - B)/2;
// If condition checks whether k lies in second half of either of the arrays
if(midA + midB < k){
// when array A has more elements than B, ignore first half of B
if(A[midA] > B[midB])
return kSmallest(A, (B+midB+1), endA, endB, (k-midB-1));
// otherwise first half of A
else
return kSmallest((A+midA+1), B, endA, endB, (k-midA-1));
}
// Else k lies in first half of either array A or B
else{
if(A[midA] > B[midB])
return kSmallest(A, B, A+midA, endB, k);
else
return kSmallest(A, B, endA, B+midB, k);
}
return -1;
}
// Driver code
int main()
{
int A[6] = {1, 2, 5, 6, 7, 9};
int B[4] = {0, 3, 8, 10};
int k = 4;
cout<<"Kth smallest number in union of A and B : "<< kSmallest(A, B, A+6, B+4, k-1);
return 0;
}
Input: (hardcoded)
int A[6] = {1, 2, 5, 6, 7, 9};
int B[4] = {0, 3, 8, 10};
int k = 4;
Output:
Kth smallest number in union of A and B : 3
Attached screenshot of code:
For question 2, extend same idea for 3 arrays, try do it on your own. Ask if you face any issue in implementation.
PS: Let me know if you have any doubt.