PantherHawk/median-of-two-sorted-arrays.md

## median-of-two-sorted-arrays.md

      
    Raw
  

              median-of-two-sorted-arrays.md
            
          
    Requirements

Return the median of two sorted arrays.
Strategy

Concatenate arrays, sort, then find median.
Justification of strategy

We want to find the median of the set of numbers provided by both arrays.
Assume we instead tried to find the medians of each array seperately and then sought the median of those medians.
Finding the median of medians will not account for the possibility that the median of both arrays already exists in of them.
Specifically, this approach fails to find the median of [1, 1] and [1, 2], returning 1.25 instead of 1.
Both arrays represent distributions.  Within each distribution exist averages: mean, mode, and median.

This problem demands we return the median of the distribution upon which both sub-distributions lie.  It might help to think of a Gaussian curve.
Both arrays form Gaussian curves.  The task is not to find the middle of each, but to find the middle of the Gaussian curve formed by both arrays.
To find the median we want a different operation depending on whether there are an even or odd number of elements in the array.
When there an odd number of elements, the median is the middle number.
When there are an even number of elements, however, we find the mean of the two middle numbers.
Define test cases


[], [1, 2] should return 1.5
[1, 1], [1, 3] should return 1
[1, 2], [2, 3] should return 2

Implementation skeleton


concatenate arrays
sort concatenated array
determine whether concatenated array has even or odd number of elements
return the median

Actual implementation

https://gist.github.com/PantherHawk/f16c0ac914ab94f3cdddf471c6b1e90b
Execute test cases

function assertArrays(a, b) {
  return JSON.stringify(a) === JSON.stringify(b) ? 'SUCCESS' : 'FAILURE';
}

assertArrays(findMedianSortedArrays([], [1, 2]), 1.5);
assertArrays(findMedianSortedArrays([1, 1], [1, 3]), 1);
assertArrays(findMedianSortedArrays([1, 2], [2, 3]), 2);

Big-O Analysis

The sorting step carries the bulk of the complexity.

Merge Sort has Big-O of O(n(log(n)).  Since the entire input is iterated over, we have (n).  But we get to each element by halving the whole input, (log(n)).
Optimization (if applicable)

Merge Sort is the fastest sorting algorithm outside of any sorting that relies on special properties of the input, like a trie/radix sort.