Exercise 21: Binary Search

The Binary Search algorithm is a simple way to find an item in an already sorted list of items. It's easily described as taking a sorted list and continually partitioning it into halves until you either find it or you run out. If you did the complete Exercise 20, then this exercise should be relatively easy.

If we want to find a number X in an already sorted list of numbers we would do this:

• Get the number in the middle of the list (M) and compare it to X.

• If X == M, you're done.

• If X > M, then find the middle of M+1 to the end of the list.

• If X < M, then find the middle of M-1 to the beginning of the list.

• Repeat, until either you find X or you have only 1 element left.

This works for anything that you can compare with equality. It will work on strings, numbers, and anything else you can order consistently.