Binary Search

Notes

Back in the days when phone numbers weren’t stored in cell phones, you might have actually had to look them up in a phonebook. How did you go about that? If you wanted to look up someone with the last name “Smith,” you could flip through the phonebook one page at a time. You don’t need to be a computer scientist to know that this is an inefficient approach.

Instead, we could start by flipping to the middle of the phonebook, and let's say we turn to a page with "M" on it. Since we know "Smith" comes after "Malan," we can literally tear the phonebook in half, throw away the left half of the phonebook, and leave ourselves with only the right half. We've just broken the problem in two!

Once again, we flip to the middle and find ourselves at “R.” We can again throw away the left half. As we continue tearing the book in half and throwing away pieces of it, we will eventually be left with a single page on which the name “Smith” appears (assuming it was there in the first place).

How do these two approaches compare in terms of their times to solve the problem?

In the graph below, the first steep line (n in red) represents the approach of turning one page at a time. The second steep line (n/2 in yellow) represents a slightly improved approach of turning two pages at a time. The curve (log n in green) represents our “tear and throw away” approach.

As the size of the problem grows, the time to solve that problem doesn’t grow nearly as quickly. In the context of this problem, n is the number of pages in the phonebook. As we go from 500 to 1000 to 2000 pages in the phonebook, we need only tear the phonebook in half at most one or two more times.

We can apply the same logic to searching for a value in an array of sorted numbers.

First, check the value stored at the middle index of the array.

We see that array[3] is 6, which is < 7. So, just as we tore off half the phone book, we can now disregard the entire left half of this array.

Next, check the value stored at the middle index of what's left of the array.

We can see that array[5] is 9, which is > 7. This time, we'll discard the right portion of what's left of the array.

array[4] == 7! We've found the value we were searching for!

This algorithm takes log n steps in the worst case. When there are only 7 array indices to check, n might not seem all that much bigger than log n. But if we have a 4 billion indices, the difference certainly matters. In that case, linear search would take 4 billion steps in the worst case, while binary search would only take 32.

Note however, that these arrays were presorted. We'll next cover sorting algorithms like bubble sort, merge sort, insertion sort, selection sort, and quick sort that can be employed if you're not lucky enough to start out with a sorted dataset!

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

Videos

study50 video thumbnail

Wednesday, Week 0

The famous phone book example
study50 video thumbnail

Wednesday, Week 3

An introduction to binary search
study50 video thumbnail

Patrick's Binary Search Short

Patrick gives a general overview