Binary Search

A binary search is a quick and efficient method of finding a specific target value from a set of ordered items. By starting in the middle of the sorted list, it can effectively cut the search space in half by determining whether to ascend or descend the list based on the median value compared to the target value.

For example, with a target value of 8 and a search space of 1 through 11:

1. The median/middle value is found and the pointer is set there, which in this case is 6.
2. The target of 8 is compared to 6. Since 6 is smaller than 8, the target must be in the higher half.
3. The pointer is moved to the next value (7) and compared to the target. It is smaller, therefore the pointer moves to the next higher value.
4. The pointer is now on 8. Comparing this to the target, it is an exact match, therefore the target has been found.

Using binary search, the target only had to be compared to three values. Compared to doing a linear search, it would have started from the very first value and moved up, needing to compare the target to eight values. A binary search is only possible with an ordered set of data; if the data is randomly arranged, then a linear search would yield results all the time while a binary search would probably be stuck in an infinite loop.