Python Data Structures and Algorithms

Binary search

A binary search is a search strategy used to find elements within a list by consistently reducing the amount of data to be searched and thereby increasing the rate at which the search term is found.

To use a binary search algorithm, the list to be operated on must have already been sorted.

The binary term carries a number of meanings and helps us put our minds in the right frame to understand the algorithm.

A binary decision has to be made at each attempt to find an item in the list. One critical decision is to guess which part of the list is likely to house the item we are looking for. Would the search term be in the first half of second half of the list, that is, if we always perceive the list as being comprised of two parts? ...