Binary search

Binary search is much faster, but it only works on a sorted list (in ascending, descending or alphabetical order). It is how you look up a word in a dictionary: open near the middle, see whether your word comes before or after, and ignore the other half.

The steps:

• Find the middle element: mid = (first + last)//2.
• If it equals the key, the search is over: found.
• If the middle element is greater than the key (in an ascending list), the key can only be in the first half: set last = mid − 1.
• If it is smaller, the key can only be in the second half: set first = mid + 1.
• Recompute mid and repeat, until the key is found or first becomes greater than last (the key is absent).

Each unsuccessful comparison halves the area to be searched, so the number of steps grows very slowly. The best case is one iteration, when the key is right in the middle. Even a list of 15 elements needs at most 4 iterations.

Example: searching for 2 in the sorted list [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43]: the middle element 17 is too big, so search the left half; its middle, 7, is too big; then 3 is too big; then 2 matches: found in 4 iterations, at position 1.

Binary search does not change the order of the list. It is used in dictionaries, telephone directories, database indexing, and the routing tables of networks.