Binary Search

Runs in O(log(n)) time.

• Put all of your items in a list.
• Sort the list in increasing order.
• Now you find items by going to the middle of the list and checking if the value here is equal, greater or less than this value. If it is equal then you are done!
• If it is less: start a new search, but treat the tested item as the upper bound of the new search. If it is more, start a new search but treat the tested item as the lower bound of the new search.

Each test cuts the amount of remaining items to be tested in half.