Searching Algorithms

Binary search

A binary search divides the search space in half for each iteration. Real life examples: guessing a number between 1 & 100, git bisect.

The tricky part of this algorithm for me is that rather than dividing up the list into smaller lists, we just need to keep track of the beginning and end of the search space. On each iteration we find the midpoint, find which side the result is on, then proceed with a narrowed beginning and ending. It is possible that the midpoint item itself could be the desired item, so there are three cases to handle.

The iterative solution seems much more natural than the recursive solution to me.