A common simple method employed by programmers to search for an item in a list is to search the entire list with a loop of some kind.

Is this how you, as an individual, would look up a name in a phone book? Or a word in an English dictionary? Note I didn’t mention anything about the list being ordered or sorted in any way. Would you painstakingly go through the entire book name by name or word by word until you’ve found what you’re looking for?

No, you would expect the book to be ordered alphabetically, and then instinctively jump to roughly the middle, and go up or down depending on whether your word is before or after the word you’ve just seen in the middle. With the remaining half of your book, above or below the words in the middle depending on the ordering, you might even jump to the middle of the remaining half, and so on, until you find your word. You know what I’m talking about, we’ve all searched through dictionaries and phone books.

This is essentially what a binary search is. We start with a sorted list, and immediately access the item deadset in the middle of the list, at the centre index. If our item we are searching for is above the centre item, we repeat the process in the latter half of the list, and find the next centre point. Otherwise we take the first half, and then look for its centre. We repeat this process until we’ve found our item.

Naturally this conforms to a recursive algorithm, as I demonstrate below (although you can use an iterative algorithm if you want, with a while loop for example). Note the midIndex +1s and -1s.. They are crucial for getting the algorithm correct. It is very easy to make a mistake here and end up with a stack overflow.

.

As we are splitting the search space up by one half each time, the time complexity is O(log2N). Note that the most efficient sorting algorithms are O(NLog2N), hence for one search a naive O(N) solution is faster. Also note that recursive algorithms will suffer a space penalty as we recurse through the stack.

Alternatively we can use an iterative solution:

Magic Index

One question from Gayle Laakmann McDowel’s book, Cracking the coding interview, is to find a magic index, from a sorted array. Taking a list or vector v, A magic index is where an index i = v[i], or where the element at i equals i. The fact the question mentions a sorted array is an immediate hint that a binary search is appropriate. The algorithm itself is almost identical to the example above: