Algorithms With JavaScript: Median of Two Sorted Arrays

Solving algorithms problems is crucial for building a solid computer science foundation for software engineers. Today we will try to solve the Median of Two Sorted Arrays.

Problem definition:

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.

Median:

First let’s figure out what median is. Median is a middle number in a sorted array. It’s obvious to select the median in an array with an odd number of elements. We simply need to divide array on right and left equal parts and element which lay between them will the the median:

[1,2,3] — median = 2

With an even number of elements we need to do some math. Our array still needs to be divided into two equal parts. And then we can calculate overage of the last element of the right side and first element of the left side:

[1,2,3,4] — [1,2] [3,4] — median = (2+3) / 2 = 2,5

Two array median

Let’s talk about finding the median in the two sorted arrays. Obviece solution will combine two…