Двоичный поиск

Держим две границы отрезка, обе включительно: lo и hi. На каждом шаге берём середину mid = (lo + hi) // 2 и сравниваем a[mid] с искомым. Возможны три случая: нашли – запоминаем позицию и выходим; a[mid] < x – искомое правее, значит lo = mid + 1; иначе – левее, значит hi = mid - 1. Цикл идёт, пока lo <= hi.

a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 23
lo = 0
hi = len(a) - 1
pos = -1
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == x:
        pos = mid
        break
    if a[mid] < x:
        lo = mid + 1
    else:
        hi = mid - 1
print(pos)   # 5

Прогон для x = 23:

Три проверки вместо десяти.

Каждый шаг делит отрезок примерно вдвое. После k шагов от исходных N элементов остаётся около $N/2^k$; отрезок станет пустым, когда $2^k$ догонит N, то есть после $\log_2 N$ шагов. В худшем случае проверок $\lfloor \log_2 N \rfloor + 1$.

Для миллиарда элементов хватает 30 сравнений – это и есть $O(\log N)$.

• Неотсортированный список. Поиск не упадёт, но молча не найдёт то, что в списке есть: сравнение с серединой отправит его не в ту половину.
• while lo < hi вместо <=. Теряется последний элемент отрезка – случай, когда lo и hi сошлись на искомом.
• lo = mid вместо mid + 1. Граница не сдвигается, отрезок перестаёт укорачиваться – вечный цикл.
• Сортировать ради одного поиска дороже, чем перебрать. Миллион элементов – около $10^6$ сравнений перебором против порядка $2 \cdot 10^7$ на сортировку. При ста запросах перебор стоит $10^8$, а одна сортировка плюс сто поисков – $2 \cdot 10^7$ и ещё две тысячи. Двоичный поиск окупается, когда запросов много.

Если в списке есть повторы, «равно» находит произвольный из них. Часто нужна не любая позиция, а граница.

Переходят на полуинтервал: lo = 0, hi = len(a), цикл while lo < hi. Сравнение a[mid] < x двигает lo вправо, иначе двигается hi. В конце lo – первый индекс, где значение не меньше x. Для правой границы условие меняется на a[mid] <= x.

a = [1, 3, 3, 3, 5, 8]
x = 3

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

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

print(left, right)      # 1 4
print(right - left)     # 3

Для x = 3 левая граница 1, правая 4, вхождений 4 − 1 = 3. Для x = 4 обе границы равны 4, вхождений 0.

Модуль bisect делает ровно это и работает за $O(\log N)$.

import bisect

a = [1, 3, 3, 3, 5, 8]
print(bisect.bisect_left(a, 3))    # 1
print(bisect.bisect_right(a, 3))   # 4

L = 2
R = 6
count = bisect.bisect_right(a, R) - bisect.bisect_left(a, L)
print(count)   # 4

bisect_left(a, x) – первый индекс, где значение не меньше x; bisect_right(a, x) – первый индекс, где значение больше x. Их разность – число вхождений. Тот же приём отвечает на вопрос «сколько чисел лежит в отрезке [L, R]»: одна сортировка и два двоичных поиска вместо перебора.