# Find Median of Two Sorted Arrays in JS

The task is taken from leetcode

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

My solution

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let i1 = i2 = 0;
let smallest, valBefore;
const pivot = Math.floor((nums1.length + nums2.length) / 2);

while (nums1[i1] || nums2[i2]) {
smallest = (nums2[i2] === void 0 || nums1[i1] < nums2[i2])
? nums1[i1++]
: nums2[i2++];

if ((nums1.length + nums2.length) % 2) {
if (pivot === i1 + i2 - 1) {
return smallest;
}
} else {
if (pivot - 1 === i1 + i2 - 1) {
valBefore = smallest
}
if (pivot === i1 + i2 - 1) {
return (smallest + valBefore) / 2;
}
}
}
};


This is the first idea that I had and it reached 99th percentile. I guess you can't take this evaluation seriously. And I'm sure there's a better solution.

• By the way, you have a bug: if the arrays are both [-1,0,1,2,3,4,5], then nums1[1]||nums2[1] will be false, and the loop will exit. Feb 13, 2022 at 17:22

The 99th percentile is due to the linear nature of your approach. The goal of this exercise is to figure out a logarithmic one.

I don't want to spell out the algorithm entirely. Just a hint to get you started. Take a middle element of nums1. Find its lower bound in nums2; call it i2. In the sorted array the selected element would be at the position nums1.length/2 + i2. I hope the hint is a good enough.

pivot doesn't look like a good name to me. totalLength, perhaps?

The complicated logic inside the loop also hurts the performance. Consider looping until you reach the midpoint:

    while (i1 + i2 < pivot)


and do the final median finding afterwards.