Searching and Sorting: K-th Element of Two Sorted Arrays

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