JavaScript Program to Find Kth Element of Two Sorted Arrays using Binary Search
Given two sorted arrays, our task is to find the Kth element in the combined array made by merging the two input arrays using Binary Search in JavaScript.
Example:
Input: Arr1: [1, 2, 5] , Arr2:[2, 4, 6, 8], K = 4
Output: Kth element is 4.
Explanation:
The final Array would be: [1, 2, 2, 4, 5, 6, 8]
The 4th element of this array is 4.
Approach
- Initialize 2 pointers for both arrays where we will mark the beginning and end of both arrays.
- After making 2 pointers each for both arrays, we will perform a binary search on the combined array to find the Kth element.
- At each step, we will compare the middle elements of both arrays.
- Adjust the pointers based on the comparison.
- Repeat the process until the Kth element is found.
Example: The example below shows JavaScript program for Kth element of two sorted arrays using Binary Search.
function findKthElement(nums1, nums2, k) {
let left1 = 0,
left2 = 0;
while (true) {
if (left1 === nums1.length)
return nums2[left2 + k - 1];
if (left2 === nums2.length)
return nums1[left1 + k - 1];
// If k is 1, return the minimum of the first elements
if (k === 1)
return Math.min(nums1[left1], nums2[left2]);
// Choose the next smallest element
let mid = Math.floor(k / 2),
index1 = Math.min(left1 + mid, nums1.length) - 1,
index2 = Math.min(left2 + mid, nums2.length) - 1,
p1 = nums1[index1],
p2 = nums2[index2];
if (p1 <= p2) {
k -= index1 - left1 + 1;
left1 = index1 + 1;
} else {
k -= index2 - left2 + 1;
left2 = index2 + 1;
}
}
}
const nums1 = [1, 2, 5];
const nums2 = [2, 4, 6, 8];
// To find 4th element
const k = 4;
console.log("Kth Element:",
findKthElement(nums1, nums2, k));
Output
Kth Element: 4
Time Complexity: O(log(min(n, m))), where n and m are the lengths of the two input arrays.
Space Complexity: O(1).