Двоичный поиск и решето — два алгоритма, которые превращают «перебор до утра» в доли секунды. Оба требуют одного условия: упорядоченности данных или монотонности проверки.
Что нужно знать
- Двоичный поиск: lo = 0, hi = n − 1; пока lo <= hi: mid = (lo + hi) // 2; сравнить a[mid] с x и сдвинуть lo = mid + 1 или hi = mid − 1. Только по отсортированному массиву.
- Шагов — около log2(n): 1000 элементов → 10, миллиард → 30.
- Первый элемент ≥ x: bisect_left(a, x); после последнего ≤ x — bisect_right.
- Поиск по ответу: нужна монотонная проверка ok(x). Ищем границу, где ok меняет значение, делением диапазона пополам.
- Решето Эратосфена до N: для p от 2, пока p · p ≤ N: если p не вычеркнуто, вычеркнуть p², p² + p, … Остаются простые.
- Делители перебирают до √n парами (i, n // i); точный квадрат даёт пару из одинаковых чисел.
- НОД — алгоритм Евклида (math.gcd), НОК = a · b // НОД.
- Целая часть корня — math.isqrt(n); int/round от n ** 0.5 на больших и «почти квадратах» ошибаются.
Где чаще всего ошибаются
- Запускать двоичный поиск по неотсортированному массиву.
- Писать while lo < hi вместо lo <= hi и терять одноэлементный отрезок.
- Начинать вычёркивание в решете с 2p и продолжать до N (верно, но медленно), либо останавливаться раньше √N.
- Считать делитель √n дважды у точного квадрата.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Алгоритмы и структуры данных · 9 класс · Двоичный поиск и целочисленные алгоритмы