simple-binary-search Algorithm
The simple-binary-search algorithm, also known as binary search, is an efficient search algorithm that works by repeatedly dividing the sorted input dataset in half. At each step, the algorithm compares the middle element of the dataset to the target value. If the middle element matches the target value, the search is successful and the position of the middle element is returned. If the target value is less than the middle element, the search continues on the left half of the dataset. Conversely, if the target value is greater than the middle element, the search proceeds on the right half. This process continues until the target value is found or the dataset is exhausted.
The binary search algorithm is highly efficient, with a time complexity of O(log n), where n is the number of elements in the dataset. This makes it an ideal choice for searching large datasets, as it can drastically reduce the number of comparisons required to find a target value compared to linear search algorithms. However, it is important to note that the binary search algorithm requires the input dataset to be sorted in order for it to function correctly. In cases where the input data is unsorted or constantly changing, other search algorithms may be more suitable.
# A binary search implementation to test if a number is in a list of elements
def binary_search(a_list, item):
"""
>>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]
>>> print(binary_search(test_list, 3))
False
>>> print(binary_search(test_list, 13))
True
"""
if len(a_list) == 0:
return False
midpoint = len(a_list) // 2
if a_list[midpoint] == item:
return True
if item < a_list[midpoint]:
return binary_search(a_list[:midpoint], item)
else:
return binary_search(a_list[midpoint + 1 :], item)
if __name__ == "__main__":
import doctest
doctest.testmod()
