Basic Algorithms: More Arrays

In simple terms the question we are asking is "Given an unsorted array of elements, return all elements where the value of the element is greater than half of the values in the array."

So for example, given an array of the elements [7,3,5,8], return 7 and 8. In the case of an odd array,  do not return the tied value, so an array such as [11,4,7,9,2], you would return 9 and 11, with 7 being the middle value.

Just thinking about it, the immediate answer that springs to mind is to take each value of the array and iterate over each other value of the array and count how many of them are smaller than the current number, if your count of numbers smaller than the current number is greater than half the length of the array, you can just add that number to the array you're going to return. That solution would look something like this



Except... that's not a very good solution. It'll run in O(n^2) time. Yuck. We don't like n^2 solutions, because they're very time consuming. Imagine if your array had a million numbers? It would take minutes to solve!

A better approach might be to consider this, the biggest half of elements would just be the first half of a sorted array! Thus if we want to make this problem trivial, all we need to do is come up with an efficient way of sorting the array, and then take half of it! I'm personally a big fan of the merge sort, but you would get the same result with a pivot sort or a quick sort. Simply sort the array, and then take the left half of it. The solution might look something like this:



This is a much better solution, with a runtime of O(nlogn). A better sort would give us a shorter time.

Some basic benchmarking, with an array with a ten thousand elements, the naive solution takes: 10 seconds, while the non-naive solution takes: 0.03. Quite a difference! This becomes more obvious in the 100,000 element array, where the naive solution takes:  834 seconds, almost 15 minutes, while the optimal solution takes 0.4 seconds!

The core takeaway of this algorithm is to always consider sorting unordered arrays when given a problem that deals with comparing values.