Двоичный поиск
В упорядоченном списке число находят двоичным поиском: смотрят на середину и отбрасывают половину, где числа быть не может. Каждый шаг вдвое сужает отрезок, поэтому в миллионе чисел хватает 20 шагов.
Границы отрезка — lo и hi, середина — (lo + hi) // 2. Поиск идет, пока отрезок не пуст: lo <= hi.
a = [2, 5, 8, 12, 16, 23, 38]
x = 23
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
print("смотрим", a[mid])
if a[mid] == x:
print("нашли на месте", mid)
break
if a[mid] < x:
lo = mid + 1
else:
hi = mid - 1
Часто нужен не сам элемент, а граница: первое место, где число не меньше x. Тогда, если a[mid] < x, граница правее середины, а иначе — в середине или левее. Отрезок [lo, hi) сужается, пока lo < hi.
Такой поиск отвечает на несколько вопросов сразу: сколько чисел меньше x, где первое вхождение x и куда вставить x, чтобы порядок не нарушился.
a = [1, 3, 3, 3, 7, 9]
x = 3
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
print(lo)
Двоичный поиск работает не только в списке. Если ответ — число и про каждое число можно проверить, подходит ли оно, ищут границу среди чисел. Целый квадратный корень из n — наибольшее k, у которого k · k ≤ n.
Когда подходящую середину оставляют в отрезке (lo = mid), середину берут с округлением вверх: (lo + hi + 1) // 2. Иначе отрезок из двух чисел не сократится и цикл не закончится.
n = 50
lo, hi = 0, n
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * mid <= n:
lo = mid
else:
hi = mid - 1
print(lo)
Итог урока. Двоичный поиск каждый шаг вдвое сужает отрезок: в упорядоченном списке он находит число или границу за log₂ n шагов.
Граница «первое место, где не меньше x» считает вхождения и числа меньше x. Поиск по ответу подбирает число, если про каждое можно проверить, подходит ли оно. При lo = mid середину округляют вверх.
В следующем уроке — префиксные суммы и два указателя: как отвечать на вопросы про отрезки списка без вложенных циклов.
Урок пройден
Двоичный поиск
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Двоичный поиск
Двоичный поиск в Python: середина (lo + hi) // 2, поиск числа и границы, подсчет вхождений, поиск по ответу и округление середины вверх. В 6 заданиях вы посчитаете шаги поиска, найдете первое вхождение и число повторов, вычислите кубический корень, подберете скорость чтения книги и прочитаете программу: что она выведет?