What's The Deal With Binary Search?

Last week in my new series of blog posts on programming concepts for liberal arts (i.e. you did not come to coding with a science or math background) programmers we discussed recursive programming. This week we are going to take a dive into another concept that is likely to come up in a technical interview, which is the binary search algorithm. The term "binary search" has the same effect on a programmer coming from a humanities or liberal arts background as "recursive programming" or even just the word "algorithm," it can cause momentary panic. But, do not panic! The key to figuring it out is to strip it of jargon and break it down into simpler ideas.

A binary search is a way to go through a group of items quicker than initiating a simple loop if you are dealing with a very large set of data. In fact, this is what you do every time you would open a phone book to search for a record (remember those huge books left at your doorstep years ago?). If I asked you to take that enormous phone book and find for me the phone number for a person named John Marcus you would not start from the first page and slowly work your way through the book until you arrived at the "M" section. Rather, you would put your finger on the outside the pages, make an educated guess where the middle of the book was and flip it open there. Then you would assess your current position to make your next move. If you had landed on the "P" records you would know that you went too far and would flip back a few pages. If you had landed on the "K" records you would know that you did not go far enough and would flip forward a few pages.

Why would you intuitively search through a phone book like that? Well, because it is a lot quicker than starting from page one and going page by page! This is exactly what the binary search algorithm is all about. It takes the phone book search and implements it over any array of data that is sorted. (Note: Your data must be sorted first for this to work effectively.)

Let's see it in code:

function binarySearch(list, value){
    var first = 0,
        last = list.length - 1,
        middle = Math.floor((last + first)/2);

    while(list[middle] != value && first < last) {
       if (value < list[middle]) {
          last = middle - 1;
        } 
        else if (value > list[middle]) {
          first = middle + 1;
        }
      middle = Math.floor((last + first)/2);
    }
 return (list[middle] != value) ? "not present" : value;
}

What are we doing here?

On lines 2-4 we are defining several key variables: first, last and middle. These variables will hold the values for us of the places in the data. We set the first variable to the first index item, the last variable to the last index item and the middle variable we define with a simple math function that gives us the middle of the data set.

On line 6 we set up a while condition that looks for two things: 1. The middle value does not equal the value we are searching for and 2. the first item is less than the last item.

If those are true we then want to know on line 7 if the value we are looking for is less than the middle of the data and, if it is, then we want to reset the last variable to equal the end of the middle value. In effect, we are chopping off the second half of the data set because we now know that our value is not there.

However, if the value we are looking for is greater than the middle of the list then we want to reset the first variable to be the next item from the middle value on line 9. While on line 11 we are setting the middle variable to be once again the middle of the last and first incorporating the new value for either last or first.

Lastly, on line 13 we are utilizing a ternary operator checking to see if it is true that the middle does not equal the value. If the middle does equal the value then we return the value and, if not, we return a simple string telling the user it is not present in the list.

I hope this was a helpful introduction to the binary search algorithm for the liberal arts coder.

Comments

[Jon Bristow]

And to those liberal arts coders who are still intimidated, please try to be kind to yourself.

I still have to break down binary search algorithms like this for a non-trivial amount of CS grads with various work histories.

Like, I don't expect you to retain the math that proves it, but it's one of the primary/simplest ways to search sorted data that's not brute force. About the only thing I'd expect more out of a CS degree person is to be able to tell me that the average access time is something to do with logarithms. officially: O(log n) Bonus if you remember that the average is also the worst case and that the best case is O(1).

I usually am not looking for you to remember that this is called a binary search. I don't like throwing terms out at people. Most of the time, I'll hand you a sorted list and ask if you can write me something that finds element X. If you give me the brute force (element 0, element 1, element 2) then I ask how you would make it faster. I'm usually looking for your thinking out loud process and whether you can stand my style of asking questions (and that I can stand your style of answering).

So... hopefully that helps people get over some of the trepidation of interviews. I know that there are some interviews that are super stressful, and some interview-ers that are looking for specific answers. But the people that you want to work for can tell the difference between quiet people and people who are legitimately out of their depth as well as people who know a lot and people who talk a lot. Try to just represent yourself as accurately and honestly as possible (while still trying to show yourself in the best possible light... you've got to be interested at least!).

[Ben Greenberg]

Jon, these are very helpful reflections. Thank you!

[Matt Hutchison]

May I suggest adding to the article that binary search only works on sorted data? Someone trying to noodle this through from an outside perspective may struggle with understanding the algorithm if they don't start from a sorted perspective.

[Ben Greenberg]

Hi Matt,

I agree, that would be helpful to put in the article. The classic phone book example makes it implicit (phone books are sorted) but I didn't say it explicitly. I'll modify the article to say it more clearly.

Thanks for the suggestion!

Ben