Median of two sorted arrays

Given two sorted arrays we have to find their median, these arrays could be of different lengths.

Example

Input: arr1 = [1,2], arr2 = [3]
Output: 2
Merged sorted array [1,2,3] and its median is 2.

Input: arr1 = [1,2], arr2 = [3, 4]
Output: 2.5
Merged sorted array [1,2,3,4] and its median is (2 + 3)/2 = 2.5.

Naive approach

In this we combine the two arrays into a single array and then sort them in ascending order and return its median.

const median = (a, b) => {
    //Sort the array
    let c = [...a, ...b].sort((a, b) => a - b);
    
    //Get the floor value
    const half = c.length / 2 | 0;
    
    //If odd then return middle element
    if (c.length % 2) return c[half];
    
    //If even then return the average of two mid elements
    return (c[half] + c[half - 1]) / 2;
}

Input:
const arr1 = [1, 12, 15, 26, 38];
const arr2 = [2, 13, 17, 30, 45, 47];
console.log(median(arr1, arr2));

Output:
17

Time complexity: O((n+m)log(n+m));
Space complexity: O(1) depending upon which sort we are using, i am considering quick sort here.

Efficient approach to find the median of two sorted arrays using binary search.

Conceptually this how it works.

As both the arrays are sorted we can perform the binary search on them.
No we have to partition the both arrays such that number of elements on left side of the both the array is same as the number of elements on the right side.
When there exists such a partition then.
If the count of combined elements in both the array is odd then return the max between the max on the left of first array and the second array.
Else return the max of the max on the left of both the arrays plus min of min of the right side of both the arrays divided by 2.

arr1 = [x1, x2, x3, x4, x5, x6];
arr2 = [y1, y2, y3, y4, y5, y6, y7, y8]

//Keep on doing this
//Dividing arr1.
leftArr1 = [x1, x2], rightArr1 = [x3, x4, x5, x6];

//Dividing arr2.
leftArr2 = [y1, y2, y3, y4, y5], rightArr2 = [y6, y7, y8];

//Till this is found
//Now when count of elements in 
left of arr1 + arr2 == right of arr1 + arr2;
2 + 5  =  4 + 3

//once found
//If total count is odd then return
max(max(leftArr1), max(leftArr2);

//Else
max(max(leftArr1), max(leftArr2)) + min(min(rightArr1), min(rightArr2)) / 2;

Iterative

const median = (nums1, nums2) => {
    //Recur in proper oder
    if(nums1.length > nums2.length) return median(nums2, nums1);
    
    const x = nums1.length, y = nums2.length;
    let lo = 0, hi = x;
     
    //Iterate to find the mid
    while(lo <= hi) {
        //Get the floor values 
        let partitionX = (lo + hi) / 2 | 0,
            partitionY = (x + y + 1) / 2 - partitionX | 0;
        
        //Get the max of first array and min of last array
        let maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
        let minRightX = partitionX === x ? Infinity : nums1[partitionX];
        
        //Get the max of second array and min of first array
        let maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
        let minRightY = partitionY === y ? Infinity : nums2[partitionY];
        
        if(maxLeftX <= minRightY && maxLeftY <= minRightX) {
            //If odd 
            if((x + y) & 1) return Math.max(maxLeftX, maxLeftY);
            //if even
            return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
        } else if(maxLeftX > minRightY) {
            //Continue the search in upperbound
            hi = partitionX - 1;
        } else {
            //Continue the search in lowerbound
            lo = partitionX + 1;
        }
    }
};

const arr1 = [1, 12, 15, 26, 38];
const arr2 = [2, 13, 17, 30, 45, 47];
console.log(median(arr1, arr2));

Output:
17

Recursive implementation of finding median of two sorted arrays using binary search

const median = (nums1, nums2, x = nums1.length, y = nums2.length, lo = 0, hi = x) => {
  //Recur in proper oder
  if(nums1.length > nums2.length) return median(nums2, nums1);
  
  if(lo <= hi){
    //Get the floor values 
    let partitionX = (lo + hi) / 2 | 0,
        partitionY = (x + y + 1) / 2 - partitionX | 0;

    //Get the max of first array and min of last array
    let maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
    let minRightX = partitionX === x ? Infinity : nums1[partitionX];

    //Get the max of second array and min of first array
    let maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
    let minRightY = partitionY === y ? Infinity : nums2[partitionY];

    if(maxLeftX <= minRightY && maxLeftY <= minRightX) {
      //If odd 
      if((x + y) & 1) return Math.max(maxLeftX, maxLeftY);
      //if even
      return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
    } else if(maxLeftX > minRightY) {
      //Continue the search in upperbound
      return median(nums1, nums2, x, y, lo, partitionX - 1);
    } else {
      //Continue the search in lowerbound
      return median(nums1, nums2, x, y, partitionX + 1, hi);
    }
  }
}

const arr1 = [1, 12, 15, 26, 38];
const arr2 = [2, 13, 17, 30, 45, 47];
console.log(median(arr1, arr2));

Output:
17

Time complexity: O(log(n + m)).
Space complexity: O(1) for iterative and O(n + m) for recursive if call stack is considered.