Binary Search

Binary search is a fast algorithm for finding a value in a sorted list. It compares the target with the middle element; if they are not equal, it throws away the half that cannot contain the target and repeats on the remaining half, until the value is found or nothing is left.

Because the search space halves at every step, binary search takes O(log n) time: about 20 comparisons are enough for a million items, compared with up to a million for a linear search. It only works on sorted data, and the same idea is used in database indexes and in "guess the number" problems.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search([2, 5, 8, 12, 16, 23, 38], 23))  # 5