Searching Smartly

Looking for your favorite book, you go to your local library but see thousands of books all around you. Out of desperation to reread your favorite book, you start at the first book

and begin your search.

After hours of going through books, you finally find your book, but by now you're too tired to read it. You later realize you could've found your book much faster since the books were in alphabetical order.

Although this divide-and-conquer approach may seem intuitive, this is actually the basis for a commonly used algorithm in computing. In order to find an element in a sorted list, programmers use binary searching.

If we assume that least → greatest follows left → right, then the procedure is as follows:

1. Determine the value of the middle element in the list

2. If this value is your desired value, then celebrate!

3a. If this value is less than your desired value, forget about all of the elements to the right of the middle element, giving yourself a new list.

3b. If this value is greater than your desired value, forget about all of the elements to the left of the middle element, giving yourself a new list.

4. Go back to Step 1 and repeat with your new list.

The GIF to the right shows how binary search would find a number. Its efficiency really shines when the list gets larger. With just 20 questions, you could guess the number I'm thinking of between one and a million. Try it out!

Next time you encounter a huge list of things to search through, don't forget about binary searching. Now if these was too easy for you and are looking for a challenge, check out sparse tables that are based on splitting up by powers of two.