Двоичный (бинарный) поиск на Python по шагам

Двоичный поиск: разбор по шагам

Двоичный поиск работает только на отсортированном списке. На каждом шаге он сравнивает искомое с серединой и отбрасывает половину, где искомого быть не может.

Список из миллиона элементов просматривается примерно за 20 сравнений.

На что смотреть в пошаговом режиме

• как меняются left, right и mid;
• сколько шагов нужно, чтобы найти число;
• что происходит, если числа в списке нет.

Код примера

a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = int(input())
left, right = 0, len(a) - 1
pos = -1
while left <= right:
    mid = (left + right) // 2
    if a[mid] == x:
        pos = mid
        break
    elif a[mid] < x:
        left = mid + 1
    else:
        right = mid - 1
print('Индекс:', pos)

Код уже в редакторе. Нажмите «По шагам» и листайте шаги кнопкой ▶ или клавишей →. Код можно менять и запускать заново.

Отладчик Python: как пользоваться и частые вопросы