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.