Бинарный поиск — объясните идею простыми словами

Работает только на отсортированном массиве. Идея как «угадай число 1–100 за минимум попыток»:

1. Берёшь середину.
2. Если искомое больше — отбрасываешь левую половину, меньше — правую.
3. Повторяешь, пока не найдёшь.

Каждый шаг режет диапазон вдвое, поэтому из миллиона элементов хватает ~20 шагов (O(log n)).

lo, hi = 0, len(a) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == x: ...
    elif a[mid] < x: lo = mid + 1
    else: hi = mid - 1