Алгоритм двоичного поиска

Двоичный поиск – базовый алгоритм на упорядоченных множествах, уменьшающий область поиска вдвое на каждом шаге. Он опирается на строгую предпосылку: монотонность целевой функции или сортированность данных по тотальному порядку. В программной практике двоичный поиск реализуется над:

1. массивом (по значению/ключу),

2. монотонным предикатом (по ответу),

3. непрерывной величиной (по вещественному ответу с точностью ε).
   Для ЕГЭ это даёт: понимание инвариантов и границ, оценку сложности O(log n), умение формулировать предикат «истина слева/справа», корректно считать границы диапазонов и количество элементов в интервале.

Математическая модель и предпосылки

• Пусть задан тотальный порядок ≤ на множестве значений.

• Массив a[0…n−1] неубывающий: a[i] ≤ a[i+1].

• Цель: по значению x найти индекс(ы) или границы элементов, удовлетворяющих отношению к x.

• Обобщение: задан монотонный по k предикат P(k) (ложь→истина или истина→ложь один раз). Требуется найти левую или правую границу переключения значения предиката.

Идея алгоритма

Поддерживаются две границы (l, r), задающие инвариантную область, в которой с гарантией лежит ответ. На каждой итерации берём середину mid и отсеиваем половину области по результату сравнения или значения предиката.

• Вычисление середины: mid = l + (r − l) // 2 (защищает от переполнения для 32-битных целых в языках C/C++/Java; в Python переполнение не актуально, но формула едина).

Корректность: инварианты и завершение

Ключ к безошибочной реализации – чёткий инвариант и согласованная схема полуинтервала.

Часто используются две канонические формы:

Форма A: закрытый интервал [l, r]

• Инвариант: ответ лежит внутри [l, r].

• Цикл: пока l ≤ r.

• Сужение:
  

  • если a[mid] < x → l = mid + 1,

  • иначе r = mid − 1.

• По выходе l – первая позиция, где мог бы стоять x (кандидат на lower_bound).

Форма B: полуинтервал [l, r)

• Инвариант: ответ лежит внутри [l, r).

• Цикл: пока l < r.

• Сужение (для «поиска левой границы»):
  

  • если a[mid] < x → l = mid + 1,

  • иначе r = mid.

• По выходе l == r – индекс левой границы (первая позиция ≥ x).

Завершение обеспечивается строгим уменьшением длины интервала (минимум на 1 каждую итерацию). Для вещественных величин – остановка по условию r − l < ε.

Практические варианты двоичного поиска

1. Поиск точного элемента (классика)
   

   Возвращает индекс x или «нет» (−1). Удобен как проверка принадлежности.

2. Границы (варианты lower_bound/upper_bound)
   

   • lower_bound(x) – первая позиция i, где a[i] ≥ x.

   • upper_bound(x) – первая позиция i, где a[i] > x.
     Тогда число элементов, равных x: upper_bound(x) − lower_bound(x).
     Число элементов в интервале [L, R]: upper_bound(R) − lower_bound(L).

3.  Поиск по монотонному предикату (двоичный поиск по ответу)
   

   Есть функция P(k), монотонная по k (например, «можно ли уложиться в k минут»). Ищем минимальный k, при котором P(k) = истина, или максимальный, где P(k) = ложь.

4. Поиск по вещественной оси
   

   Для непрерывных функций/величин (порог, корень уравнения, оптимальная длина) – итерации до точности ε.

5.  Дубликаты и убывающие массивы
   

   • При наличии дубликатов используйте границы, а не «классический» поиск.

   • Для убывающего массива меняются направления сравнений (или ищем по ключу −a[i] с теми же правилами).

Сложность и ресурсы

• Ассимптотика: O(log n) сравнений; память: O(1) (итеративно) или O(log n) стек (рекурсивно).

• На практике погрешности в границах – главная причина ошибок и зацикливаний.

Типичные ошибки (и как их избежать)

1. Неправильное вычисление mid: берите l + (r − l) // 2.

2. Несогласованные границы: выбрали [l, r) – не используйте while (l ≤ r).

3. Не меняется интервал: обновляйте l на mid + 1 или r на mid/mid − 1.

4. Неверная остановка для вещественных: используйте условие по ε, а не «равенство».

5. Забыли монотонность в поиске по ответу: доказуйте/проверяйте, что P(k) действительно монотонен.

6. Работа с дубликатами: используйте lower_bound/upper_bound для счёта и диапазонов.

Реализации (псевдокод / Python)

1. Классический поиск (есть ли x в a), [l, r]
   

   def binary_search(a, x):

       l, r = 0, len(a) - 1

       while l <= r:

           mid = l + (r - l) // 2

           if a[mid] == x:

               return mid

           if a[mid] < x:

               l = mid + 1

           else:

               r = mid - 1

       return -1

2. Левая и правая границы, [l, r)
   

   def lower_bound(a, x):  # первая позиция i: a[i] >= x

       l, r = 0, len(a)

       while l < r:

           mid = l + (r - l) // 2

           if a[mid] < x:

               l = mid + 1

           else:

               r = mid

       return l

   
   

   def upper_bound(a, x):  # первая позиция i: a[i] > x

       l, r = 0, len(a)

       while l < r:

           mid = l + (r - l) // 2

           if a[mid] <= x:

               l = mid + 1

           else:

               r = mid

       return l

3. Поиск по монотонному предикату: минимальный k с P(k)=True
   

   def first_true(P, lo, hi):  # ищет на [lo, hi], возвращает минимальный k

       l, r = lo, hi

       while l < r:

           mid = l + (r - l) // 2

           if P(mid):

               r = mid

           else:

               l = mid + 1

       return l  # проверить, что P(l) == True

4. Вещественная версия по точности ε
   

   def binary_real(f, left, right, eps):

       l, r = left, right

       while r - l > eps:

           mid = (l + r) / 2

           if f(mid):      # монотонный булев предикат по x

               r = mid

           else:

               l = mid

       return (l + r) / 2

Связь с подготовкой к ЕГЭ

• Алгоритмы и программирование: реализация поиска, границы, подсчёт в интервале.

• Анализ сложности: сравнение линейного и логарифмического подходов.

• Обработка файлов: быстрый подсчёт количества значений, попавших в диапазон [L, R], через upper_bound − lower_bound.

• Моделирование: двоичный поиск по ответу (минимальное время/порог), доказательство монотонности предиката.

• Вещественные вычисления: погрешность, ε-остановка.

Пять упражнений с подробным разбором

Упражнение 1. Классический поиск элемента

Задание. Дан отсортированный по неубыванию массив
a = [1, 3, 3, 7, 9, 11, 15].
Найдите индекс x = 7 классическим двоичным поиском. Покажите последовательность (l, r, mid).

Решение.

• Старт: l=0, r=6, mid=3 → a[3]=7 == x ⇒ нашли, индекс 3.
  Вывод. В лучшем случае ответ находится за 1 шаг; сложность – O(log n) в общем виде.

Упражнение 2. Подсчёт количества значений в интервале

Задание. Дан отсортированный массив a = [2, 4, 4, 5, 7, 9, 9, 12, 13].
Сколько элементов попадает в интервал [4, 9]? Используйте lower_bound(4) и upper_bound(9).

Решение.
lower_bound(4) = 1 (первая позиция a[i] ≥ 4).
upper_bound(9) = 7 (первая позиция a[i] > 9 – индекс 7, так как a[6]=9, a[7]=12).
Количество = 7 − 1 = 6 (элементы с индексов 1…6 включительно).
Пояснение. При больших n метод работает за O(log n) вместо O(n).

Упражнение 3. Количество вхождений значения (дубликаты)

Задание. Массив a отсортирован. Требуется вернуть число вхождений x.
Примените границы к массиву из Упр. 2 для x = 4 и для x = 9.

Решение.
Число вхождений x = upper_bound(x) − lower_bound(x).

• Для x=4: lb=1, ub=3 ⇒ 3−1=2.

• Для x=9: lb=5, ub=7 ⇒ 7−5=2.

Вывод. Корректная работа с дубликатами без линейного прохода.

Упражнение 4. Поиск по ответу (монотонный предикат)

Задача (тип ЕГЭ продвинутого уровня). Есть n работ с объёмами t[i]. Имеется m одинаковых исполнителей; за 1 минуту каждый выполняет 1 единицу объёма. Можно ли завершить все работы за T минут? Предикат P(T) истинный, если sum(min(t[i], T)) ≤ m*T. Требуется найти минимальное T, при котором P(T)=истина.

Решение-эскиз.

1. Предикат монотонен: если можно за T, то можно за T+1.

2. Ищем T на [0, max(t[i])] (или шире) двоичным поиском:
   

   def feasible(T, t, m):

       return sum(min(x, T) for x in t) <= m*T

   
   

   def min_time(t, m):

       l, r = 0, max(t)  # верхняя оценка

       while l < r:

           mid = l + (r - l) // 2

           if feasible(mid, t, m):

               r = mid

           else:

               l = mid + 1

       return l  # минимальное T

Пояснение. Классический «поиск по ответу»: логарифмический перебор по времени.

Упражнение 5. Вещественный двоичный поиск (точность ε)

Задание. Найдите квадратный корень √S для S = 10 с точностью ε = 1e−6 двоичным поиском на отрезке [0, max(1, S)].

Решение.
Монотонный предикат: f(x): x*x ≥ S. Ищем минимальный x, где условие истинно.

def sqrt_bin(S, eps=1e-6):

    l, r = 0.0, max(1.0, float(S))

    while r - l > eps:

        mid = (l + r) / 2

        if mid * mid >= S:

            r = mid

        else:

            l = mid

    return (l + r) / 2

Для S=10 результат ≈ 3.162277 с требуемой точностью.
Замечание. Для вещественных величин критична остановка по r − l > ε.

Контрольный список «Правила двоичного поиска»

1. Определите инвариант: ответ лежит в [l, r] или [l, r).

2. Единообразие формы: для [l, r) используйте while l < r и обновления r = mid или l = mid + 1.

3. Середина безопасно: mid = l + (r − l) // 2.

4. Дубликаты – через границы: lower_bound, upper_bound.

5. Интервалы быстро: количество в [L, R] = upper_bound(R) − lower_bound(L).

6. Поиск по ответу: докажите монотонность P(k), задайте корректный диапазон, ищите первую истину/последнюю ложь.

7. Вещественные: работайте по ε, а не по «равно».

8. Проверяйте крайние случаи: пустой массив, x меньше минимума/больше максимума, все элементы одинаковы, n=1.

9. Убывающие данные: инвертируйте сравнения или значения.

10. Тестируйте пошагово: расписывайте (l, r, mid) – это предотвращает зацикливание.

Заключение

Двоичный поиск – «рабочая лошадка» алгоритмики: он прост по идее, но требователен к строгости границ и инвариантов. Владение его формами (классика, границы, поиск по ответу, вещественный вариант) и умение считать интервальные количества – компетенции, которые напрямую конвертируются в баллы на ЕГЭ и в практическую эффективность программ.