Busca Binaria — O(log n)

Funciona em arrays ordenados. Divide o espaco de busca pela metade.

Tempo: O(log n)
Espaco: O(1)
Python
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
Python
    while lo <= hi:
mid = (lo + hi) // 2
Python
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

1 milhao de elementos → ~20 passos. 1 bilhao → ~30 passos!