Algorithms
What Is Binary Search?
Binary search finds a value in a sorted list by checking the middle item and discarding half of the remaining list at each step.
Definition
Binary search is a fast way to find an item in a sorted list. It looks at the middle item first. If the target is smaller, it searches the left half; if larger, the right half. It repeats until it finds the item or runs out of list.
Each step halves the search space, so a list of one million items needs at most about 20 comparisons.
How it works
Keep two markers, low and high, around the part of the list that could still hold the target. Compute the middle index, compare, and move one marker past the middle. Stop when the markers cross.
The running time is O(log n). The list must already be sorted; sorting it first costs O(n log n), which only pays off if you search it many times.