Bite 40. Write a binary search algorithm

There are many ways to search for an item in an ordered collection. One of the slowest methods is to check each single item from beginning to end. A more popular algorithm is binary search:

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

Your task today, should you decide to accept it, is to implement a binary search algorithm. Yes, Python has built in features that make this a no-brainer, but it’s also good to know how some things are done under the hood. It’ll make you a better programmer in the long run.