Problem Statement:
You are given 2 arrays that are sorted.
You need to find the k’th element if the two arrays are sorted and merged.
Example
Array 1 - 1 3 5 Array 2 - 2 4 6 k = 3 Sorted array = {1, 2, 3, 4, 5, 6} The 3rd element of the array is sorted = 3
Solution
We have number of methods to solve this problem:
Method 1: Naive Approach
Merge the two arrays and then get the element at the kth index.
Time Complexity: O(n)
Method 2: Binary Search Approach:
In this method, we find the middle element in arr_1 and arr_2.
Lets call them mid_1, mid_2.
If arr_1[mid_1] is less than k, then the elements after mid_2 cannot be the required element.
Set the last element of arr_2 to be arr_2[mid_2]
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <sstream> using namespace std; int kth_element_brute_force(int arr1[], int arr2[], int m, int n, int k) { int sorted[m + n]; int i = 0; int j = 0; int d = 0; while (i < m && j < n) { if (arr1[i] < arr2[j]) sorted[d++] = arr1[i++]; else sorted[d++] = arr2[j++]; } while (i < m) sorted[d++] = arr1[i++]; while (j < n) sorted[d++] = arr2[j++]; return sorted[k - 1]; } int kth_element_binary_search(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_element_binary_search(arr1, arr2 + mid2 + 1, end1, end2, k - mid2 - 1); else return kth_element_binary_search(arr1 + mid1 + 1, arr2, end1, end2, k - mid1 - 1); } else { if (arr1[mid1] > arr2[mid2]) return kth_element_binary_search(arr1, arr2, arr1 + mid1, end2, k); else return kth_element_binary_search(arr1, arr2, end1, arr2 + mid2, k); } } int main() { int arr1[3] = {1, 2, 5}; int arr2[4] = {1, 4, 7, 8}; int k = 5; cout <<"The kth element using brute force is = " <<kth_element_brute_force(arr1, arr2, 5, 4, k)<<endl; cout <<"The kth element using binary search is = " <<kth_element_binary_search(arr1, arr2, arr1+3, arr2+4, k-1)<<endl; return 0; }
Output:
The kth element using brute force is = 5 The kth element using binary search is = 5