One search to rule them all

This is the third in a series about core data structures and algorithms.

The outstanding characteristic of binary search is that it’s intuitive. Many algorithms are not, but binary search is what people — anyone, not just programmers — naturally execute when looking for an item in a sorted data set.

Given a sorted data set, which supports random access, binary search is the only game in town. And it’s fast. Only using a hash table is faster, but that means doubling the storage requirements.

How fast?

Binary search runs in logarithmic time, O(log(n)). What does this mean in practice? Well, if you had a single record for every person on earth (7.6 billion records as of November 2017), those records were sorted, and it took a millisecond to check a record, you could find a matching record in, at most 33 milliseconds. This shows you the power of eliminating half the records each search. And if the human species became interplanetary, with 7.6 billion individuals on each of 10 planets, the search time increases to just 37 milliseconds.

So binary search is very fast. If you have an ordered dataset, and you can randomly access it, it’s the only search you need.

It’s also robust

Binary search can be used in more applications than just locating a single element. It can be used to find the target range in a sorted dataset (not just an element), and it can even be used to quickly find a discontinuity in a dataset. Its applications are quite broad.

So consider sorting your data

If you have a set of data, from which you repeatedly need to find different elements, consider sorting it. While sorting will take time, the ability to perform binary search will make it worth it.

Leave a Reply

Your email address will not be published. Required fields are marked *