If your college computer science algorithm and data structure knowledge is a little rusty, let’s start with a high level view of what binary search is from a real world example. Imagine that we lived in a world that still used printed dictionaries.

What would the algorithm look like to find the word “Motorcycle”? We could go with the naive approach and start at the beginning of the dictionary and look at each word until we get to “motorcycle”. However that would force us to traverse thousands of words for no reason. That’s not the way that we’d lookup a word in the dictionary, so that’s probably a good indicator that there’s a better option in the computer science world as well. How would you find “motorcycle” in the dictionary? You’d open the dictionary up in the middle, if you landed on a page where all the letters begin with “O” you would know to flip to the left, if you run into the “L’s” you know you need to move slightly to the right. You’d continue this process until you found “Motorcycle”.

So binary search is faster than simply going word by word, but how much faster is it exactly? And write this down since it could be asked by an interviewer:

Binary search runs in O(lg n) time complexity.

This is very fast, in fact, even if you used binary search on a dictionary with millions of hypothetical words you’d be able to find the target word in around 20 page turns. This would be compared with the naive approach that would take tens of thousands of page turns.

So now that you have a good idea on how binary search works at a high level, let’s walk through a technical example. Imagine you had an array of values such as this:

How would we find the “19” value? Keeping our Dictionary example in our mind, we’re going to utilize the same principle to quickly find the “19” with binary search.

Here you can see what a binary tree looks like. There are a few rules that binary trees need to follow in order for us to search through them:

1. Each node has the ability to have, at most, two child nodes.
2. The child node on the left has to be less than the parent node
3. The child node on the right has to be greater than or equal to the parent node

As you can see this tree obeys each of these rules, which means that we can utilize binary search to find the “19” value. The process is as follows:

1. We start at the root node, in this case it’s 10, and since the target value is greater than 10, we can immediately ignore the left side of the tree, cutting our collection by over 50% right away.
2. Looking at the value 20, we know that 19 is less than 20 so we move to the left.
3. Lastly we see that we’ve arrived at the target value and our search is over.

This only took 3 comparisons to get to the 19 value, which is much faster than if we had simply started at the beginning of the array and iterated through it until the target was found.

Obviously with a small array like this it would be easy to iterate through and get the 19th value. However this is a base case, binary search makes it possible to search through millions of values in a very efficient manner.

In summary, some keys to remember in order to properly answer binary search interview questions are:

1. Binary trees are a data structure
2. They need to be sorted to be valid
3. Each node can have up to two child nodes
4. To search through the tree you recursively traverse the tree and move left for lower values and right for greater than or equal to values
5. Binary search runs in O(lg n) time complexity

I hope that this has been helpful and will help you answer any binary search interview questions that arise in a coding interview. In the show notes I’ve also included a link to the animation that I used in the video so you can play with the algorithm yourself.

Resources

• Binary Search Tree Algorithm