Binary Search Explained

For the uninitiated there are a lot of intimidating buzz words that get thrown around when you listen in on programming discussions. Recursion, hash tables, bitwise operators, and bash commands may seem complicated and mysterious at first but ultimately learning to program is no different than learning any other skill. It starts out difficult and confusing but gradually you begin to understand and eventually master each skill. This blog post is about one of those buzz words that might seem intimidating at first but in reality is a simple and powerful concept.

What Is Binary Search? #

A binary search is an effective method for searching for a piece of information inside of a huge dataset.

A binary search goes something like this:

Imagine that you are a machine and you are looking for someone’s name in the phonebook. The name you are looking for is “Scott” and for the sake of this example we are assuming you can’t flip directly to the “S” section. One way you could search the phonebook is to start at the very beginning and check each name to see if it matches with Scott. The worst case scenario for this type of search is that you go through the entire book and Scott’s name is the last name. This method could potentially take you a lot of time.

The way the binary search works is that you would begin searching the phonebook by looking at the name in the very middle of the book. Let’s say the name that you find in the very middle is Michael. You would check to see if the name Michael comes before or after Scott.

Michael obviously lies alphabetically before Scott in our ordered phone book so we know that Scott can’t be in the first half of the book. So we chop the first half of the phonebook off. We have effectively eliminated half of the possible locations where Scott could be.

We then repeat the process with the remaining half of the book. We look at the middle and check to see if the middle name is before or after Scott. We then chop off the half that Scott isn’t in and we repeat the process. Each time we do this process we cut out half of the locations that we would need to search. We repeat the process until the name we land on is Scott.

Why is this such a powerful search method? Imagine that there are a million names in the phonebook. If we used a binary search method then we would only have to repeat this process at most twenty times! Compare twenty iterations with the the worst case scenario of looking at each name in the phonebook starting from the beginning. There is no comparison.

An important note: in order to perform a binary search your information must be sorted. If the information isn’t sorted then a binary search method would obviously be worthless.