How to use Modified Binary Search In Javascript
We will first check if lengths of array are equal or not. Then we apply Binary search to find the correct position to partition the arrays. Now we find the maximum and minimum values on the left and right sides of the partition for both arrays and Check conditions for median if the total number of elements is even or odd. Return the median value accordingly . If condition is not met we Adjust partition based on conditions and Repeat the binary search process until median is found. When the correct partition is found, return the calculated median value.
Example: To demonstrate finding Median of 2 sorted arrays of equal size using merging
function findMedianSortedArrays(nums1, nums2) {
const m = nums1
.length;
const n = nums2
.length;
if (m > n) return findMedianSortedArrays(nums2, nums1);
let low = 0;
let high = m;
while (low <= high) {
const partitionX = Math
.floor((low + high) / 2);
const partitionY = Math
.floor((m + n + 1) / 2) - partitionX;
const maxX = partitionX === 0 ?
Number.NEGATIVE_INFINITY : nums1[partitionX - 1];
const maxY = partitionY === 0 ?
Number.NEGATIVE_INFINITY : nums2[partitionY - 1];
const minX = partitionX === m ?
Number.POSITIVE_INFINITY : nums1[partitionX];
const minY = partitionY === n ?
Number.POSITIVE_INFINITY : nums2[partitionY];
if (maxX <= minY && maxY <= minX) {
if ((m + n) % 2 === 0) {
return (
Math
.max(maxX, maxY)
+
Math
.min(minX, minY)) / 2;
} else {
return Math.max(maxX, maxY);
}
} else if (maxX > minY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
}
const nums1 = [1, 2, 3];
const nums2 = [4];
console.log(findMedianSortedArrays(nums1, nums2));
Output
2.5
Time Complexity: O(log(min(m,n)
Space Complexity: O(1)
Median of 2 Sorted Arrays of Equal Size using JavaScript
The median is the middle element of the array. If several elements are odd then the middle element is the median and if several elements are even then the average of the two middle values is the median after arranging the array in sorted order.
Below are the approaches to find the median of 2 sorted arrays of equal size using JavaScript:
Table of Content
- Using Simple merging
- Using Modified Binary Search
Contact Us