Binary search is considered to be one of the fastest search algorithms. Given a sorted data collection of ordinally (order of magnitude) distinguishable values, the algorithm requires at most half the number of data records in steps to ensure whether or not a certain value is included.
Because of the high speed of this method, many operating systems that utilise an indexing scheme use this algorithm.
How exactly does it work? It’s quite simple. Starting from a sorted data set of numbers and a target value, it first determines the middle entry. This should not be confused with the median, where the lower of the middle 2 is used as the reference value for an even number of data records. If this value equals the target value, it terminates successfully. However, if the value is smaller than the searched value, it repeats the process with the larger half. If the opposite is true (average value > target value), it continues with the lower half instead. The process does not stop until the value has been found or all entries in the search list have been covered.
Summarized in keywords:
Initial components
– A sorted data set
– A target value
Approach
- Determine the value in the center (leftmost on even number of elements)
- Compare the central value with the target:
a. Central > Target -> Reduce scope to lower half
b. Central == Target -> Terminate successfully
c. Central < Target -> Reduce scope to higher half - If the target has not been found and values remain in scope -> repeat step 2
In contrast to the cliché in programming ‘easier said than done’, transferring the concept to (Python) code is child’s play.
def binary_search(target_value: int, entries: list):
num_entries = len(entries)
if num_entries == 0:
return False
if num_entries == 1:
return entries[0] == target_value
index_center = num_entries // 2
median = entries[index_center]
if target_value == median:
return True
elif target_value > median:
return binary_search(target_value, entries[index_center:])
elif target_value < median:
return binary_search(target_value, entries[:index_center])
return False
EN 
DE