Press "Enter" to skip to content

Find Median from Numbers Array

Ajk 0

How to find median from numbers array? This is quite the popular interview question. Ah, maths… Such a beautiful subject and so inter-related to computer science. Before we start thinking of algorithms let us remember what a median is. Quite literally from the dictionary definition:

Median: Arithmetic, Statistics. the middle number in a given sequence of numbers, taken as the average of the two middle numbers when the sequence has an even number of numbers:
4 is the median of 1, 3, 4, 8, 9.

So in a way, we care about the midpoint value if we were to sort the numbers.

Does not sound too hard, does it? Before we jump head first into the problem, we have to discuss constraints and requirements. The definition itself is clear, but what would happen if we were to have an even number of elements in the array? In that case there would be no single midpoint median.

Well as it turns out, per Wikipedia’s explanation:

If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values.

A quick visual representation is shown below with odd or even number of elements.

Find Median from Numbers Array
Finding The Median

If you are interested in a better statistical scientific explanation of the median you can look at Wolfram MathWorld.

So as it seems we only have to sort the array and then find the midpoint. So let us try that solution out!

How to Find Median from Numbers Array – Basic Algorithm

  • Sort the numbers array.
  • Get the item in the middle of the list. (Or the average of the two, in case of even elements)

Sounds pretty easy, doesn’t it!! So let us just get our hands to it and try to program a solution that will generate all permutations of an array or string in PHP.

How to Find Median from Numbers Array in PHP

As you can see, we also got to a special case that we did not think of at the beginning (mistake on our part). We had not considered what would happen, were the array to be empty. In this case we decided to simply return null, thought throwing an Exception could also be valid.

The analysis is pretty straight forward with O(Nlog(N)) time complexity, which is bottlenecked by the sorting technique and O(1) space complexity, assuming an in-place sorting. (Food for thought? Can you remember such a sorting algorithm? Hint Hint!

On another note, the code writing was done pretty fast. But to make sure that we did not get any advantage due to the scripting nature of PHP let us try to write the solution in Java too. Would anything change? Well for one, we cannot have an ambiguous number type. Java’s arrays would need to be of a specific type. The return value also needs to be able to support floating point numbers, therefore it has to be a float.

Assumption: The input array is made of integers. Return value is a float.

How to Find Median from Numbers Array in Java

As you can see not much changed, except for a few tweaks per the language in the way we checked for edge cases, how we found our midpoint and massaged the output to always be the correct float.

Alright, this was a first post on How to Find Median from Numbers Array. In a subsequent post (part II) I will go into detail on a follow up question. What if instead of a static array input, we would get a stream of information. Meaning we get to choose how this data is stored as it comes in (rather than simply have it in a default array)!

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂