Двоичный и тернарный поиск

Найдём 8 в [1,3,5,7,8,10,13]. Средняя ячейка содержит 7: первые четыре значения не подходят. В оставшейся части среднее равно 10: всё правее него слишком велико. Осталась ячейка с 8. За три сравнения исключили почти весь массив; попробуйте выбирать следующую половину самостоятельно в модели.

В предыдущих лекциях мы получали упорядоченный массив. Теперь воспользуемся его порядком. Если A отсортирован по возрастанию и средний элемент меньше x, то все элементы левее тоже меньше x. Одно сравнение позволяет исключить сразу половину кандидатов, а не одну позицию.

Для массива [1, 3, 3, 8, 10] поиск значения 3 может вернуть любую из двух равных ячеек. Однако в задачах часто требуется первая позиция, место для вставки или количество вхождений. Удобнее сразу искать определённую границу, а проверку равенства делать после.

Lower bound (Lower bound) — Индекс первого элемента массива, который не меньше x; если такого нет, возвращается n.

Условие A[i] ≥ x на отсортированном массиве имеет вид «ложь, ложь, …, истина, истина». Ищем первый индекс, где оно истинно. Если таких элементов нет, возвращаем n — позицию сразу после массива. Так lower bound определён и для отсутствующего x.

Предварительная сортировка не бесплатна. Для одного поиска в неупорядоченном массиве обычно достаточно O(n)-прохода. Сортировать имеет смысл, когда данные уже упорядочены или запросов много: стоимость подготовки тогда оплачивается один раз.

Идея деления пополам проста, но ошибки обычно возникают в границах. Зафиксируем точный смысл левой и правой границы, чтобы из него следовали и обновления, и условие остановки.

После сравнения A[mid]=7 с целью 8 можно исключить и сам mid, и всё слева: left = mid+1. Если A[mid]=10, этот индекс ещё может оказаться первой подходящей позицией, поэтому right = mid. Именно эти два действия выполняет модель.

Храним полуинтервал ещё не проверенных позиций [left,right). Все индексы меньше left заведомо содержат значения < x; все действительные индексы начиная с right содержат значения ≥ x. Ответ-граница находится между left и right включительно, в том числе может быть n.

left = 0; right = n
while left < right:
    mid = left + (right-left)//2
    if A[mid] >= x:
        right = mid
    else:
        left = mid+1
return left

Если mid подходит, right=mid сохраняет его как возможный ответ; иначе left=mid+1 исключает уже проверенную ячейку. На каждом шаге число неизвестных позиций строго уменьшается. При left=right их нет: left — первая подходящая позиция или n. Это доказывает и корректность, и завершение.

Для пустого массива left=right=0 — ни одного чтения. Для [8] и x=8 выполняется right=0; для x=9 выполняется left=1. Чтобы проверить точное наличие значения, после поиска нужны обе проверки: left < n и A[left] == x. Время O(log(n+1)), дополнительная память O(1).

Смысл [left,right) теперь одинаков в модели и коде. Изменим только строгость проверки и получим вторую полезную границу.

В [1,3,3,8,8] число 3 занимает индексы 1 и 2. Первая позиция ≥3 равна 1, первая позиция >3 равна 3. Это lower_bound и upper_bound. В обоих случаях начальные границы 0,n, цикл left<right, обновления right=mid и left=mid+1; меняется только условие good.

Границы помогают искать и соседей. Индекс последнего элемента меньше x равен lower−1, но он существует только при lower > 0. Первый элемент больше x находится на upper, но обращаться к нему можно только при upper < n. Возвращённая позиция вставки сама по себе не гарантирует существования элемента.

В коде Python и Rust ниже два поиска отличаются только строгостью сравнения. Попробуйте заранее определить результат для пустого массива, x меньше минимума и x больше максимума — эти случаи проверяют, действительно ли вы понимаете смысл возвращаемого индекса.

def bound(a: list[int], x: int, upper: bool = False) -> int:
    left, right = 0, len(a)
    while left < right:
        mid = left + (right - left) // 2
        good = a[mid] > x if upper else a[mid] >= x
        if good: right = mid
        else: left = mid + 1
    return left

data = [1, 3, 3, 5, 8, 8, 8, 10]
lo, hi = bound(data, 8), bound(data, 8, True)
print(lo, hi, hi - lo)

fn bound(a: &[i64], x: i64, upper: bool) -> usize {
    let (mut left, mut right) = (0,a.len());
    while left < right {
        let mid = left + (right-left)/2;
        let good = if upper { a[mid] > x } else { a[mid] >= x };
        if good { right=mid; } else { left=mid+1; }
    }
    left
}

fn main() {
    let data=[1,3,3,5,8,8,8,10];
    let lo=bound(&data,8,false); let hi=bound(&data,8,true);
    println!("{} {} {}",lo,hi,hi-lo);
}

4 7 3

Во всех этих запросах граница находилась среди индексов массива. Но самому алгоритму массив не нужен: достаточно уметь проверять монотонное условие для выбранного кандидата. Перенесём поиск на числовое значение ответа.

def lower_bound(a, x):
	# Напишите решение здесь
	pass

Сначала простой вопрос: нужно накопить не менее 12 монет, а каждый день добавляет 3. Для 2,3,4,5 дней ответы «нет, нет, да, да». Первое подходящее число дней равно 4. После первого «да» ответ снова не станет «нет» — это и есть свойство, которое позволяет делить диапазон пополам.

Пусть требуется минимальное значение параметра, при котором задачу можно выполнить. Вместо прямого построения оптимума спросим: можно ли выполнить задачу при фиксированном X? Если увеличение X не превращает возможное в невозможное, получаем тот же переход «нет → да».

Монотонный предикат (Monotone predicate) — Булева функция, у которой на упорядоченной области сначала все false, затем все true (или наоборот).

Рассмотрим n прямоугольников a×b без поворотов, которые размещаются рядами и столбцами в квадрате. При стороне x в ряд помещается ⌊x/a⌋ прямоугольников, а рядов помещается ⌊x/b⌋. Требуется вместить не меньше n штук.

Если сторона x подходит, любая большая тоже подходит. Ищем первую допустимую целую сторону тем же циклом left<right: при fits(mid) делаем right=mid, иначе left=mid+1. Начинаем с left=0 и заведомо достаточной right=max(a,b)·n: в такой квадрат точно поместится ряд из n прямоугольников. Для другой проверки верхнюю границу можно искать удвоением. Если right не гарантирует ответ, поиск способен вернуть неверную границу.

Одна проверка здесь занимает O(1) машинных арифметических операций, поэтому время — O(log R), где R — найденная верхняя граница. В других задачах проверка может просматривать n элементов: тогда общая оценка будет O(n log R). Название «двоичный поиск» само по себе не задаёт полную сложность.

Python использует целые произвольной точности, а пример Rust считает в u128 при явно ограниченных w,h,n. Даже если границы поиска помещаются в i64, произведение двух частных может оказаться больше. В общем случае используйте подходящий широкий тип или безопасное сравнение через деление.

def square_side(w: int, h: int, n: int) -> int:
    assert 1 <= w <= 10**9 and 1 <= h <= 10**9 and 1 <= n <= 10**9
    left, right = 0, max(w, h) * n
    while left < right:
        mid = left + (right - left) // 2
        if (mid // w) * (mid // h) >= n: right = mid
        else: left = mid + 1
    return left

print(square_side(3, 2, 12))

fn square_side(w: u64, h: u64, n: u64) -> u128 {
    assert!((1..=1_000_000_000).contains(&w));
    assert!((1..=1_000_000_000).contains(&h));
    assert!((1..=1_000_000_000).contains(&n));
    let (w,h,n)=(w as u128,h as u128,n as u128);
    let (mut left,mut right)=(0,w.max(h)*n);
    while left<right {
        let mid=left+(right-left)/2;
        if (mid/w)*(mid/h)>=n { right=mid; } else { left=mid+1; }
    }
    left
}

fn main() { println!("{}", square_side(3,2,12)); }

9

Мы заменили оптимизацию проверкой допустимости. Этот же приём особенно полезен, когда ответ определяется максимумом нескольких величин: проверка общего ограничения может оказаться проще прямой минимизации.

def fits(x, a, b, n):
	# Напишите решение здесь
	pass

Два участника стоят в 0 и 10 и идут со скоростью 1. За t=4 они достигают [−4,4] и [6,14]: встреча невозможна. При t=5 интервалы соприкасаются в точке 5 — оба придут одновременно. При t=6 мест встречи уже много. Сначала подвигайте время в модели, затем сравните случай нескольких участников.

Пусть участники находятся в точках xᵢ на прямой и движутся со скоростями vᵢ > 0. Нужно выбрать место встречи p так, чтобы последний участник пришёл как можно раньше. Для фиксированной точки p время встречи равно maxᵢ |p−xᵢ|/vᵢ, а искать нужно минимум этого выражения по p.

Вместо выбора точки зафиксируем время t и спросим, существует ли хотя бы одно общее место встречи к этому моменту. Участник i за это время достигает любого места из отрезка [xᵢ−vᵢt, xᵢ+vᵢt]. Все должны выбрать одну и ту же точку, поэтому нужно пересечение всех отрезков.

Для проверки достаточно найти самую правую левую границу L и самую левую правую границу R. Если L ≤ R, любой p из [L, R] подходит; если L > R, общего места нет. Один проход по участникам стоит O(n).

При увеличении t каждый отрезок только расширяется, поэтому непустое пересечение уже не исчезнет. Получен монотонный предикат для двоичного поиска по времени. При k итерациях полная работа равна O(kn), а не O(k). Положительные скорости гарантируют существование конечного подходящего времени; нулевые скорости потребовали бы отдельного разбора.

def meeting_time(people: list[tuple[float, float]]) -> float:
    assert people and all(v > 0 for _, v in people)
    def feasible(t: float) -> bool:
        return max(x-v*t for x,v in people) <= min(x+v*t for x,v in people)
    left, right = 0.0, 1.0
    while not feasible(right): right *= 2
    for _ in range(100):
        mid = (left + right) / 2
        if feasible(mid): right = mid
        else: left = mid
    return right

print(f"{meeting_time([(7.0,1.0),(1.0,2.0),(3.0,1.0)]):.6f}")

fn meeting_time(people: &[(f64,f64)]) -> f64 {
    assert!(!people.is_empty() && people.iter().all(|&(_,v)|v>0.0));
    let feasible=|t:f64| {
        let left=people.iter().map(|&(x,v)|x-v*t).fold(f64::NEG_INFINITY,f64::max);
        let right=people.iter().map(|&(x,v)|x+v*t).fold(f64::INFINITY,f64::min);
        left<=right
    };
    let (mut left,mut right)=(0.0,1.0);
    while !feasible(right) { right*=2.0; }
    for _ in 0..100 {
        let mid=(left+right)/2.0;
        if feasible(mid) { right=mid; } else { left=mid; }
    }
    right
}

fn main() { println!("{:.6}",meeting_time(&[(7.0,1.0),(1.0,2.0),(3.0,1.0)])); }

2.000000

В отличие от стороны квадрата, время встречи — вещественный ответ. У него нет следующего целого: обновление left=mid+1 потеряло бы часть допустимых времён. Уточним, как вместо дискретного сужения задать требуемую точность и число итераций.

Пусть ответ лежит на [0,10], а нужна абсолютная ошибка не более 0.001. После 14 делений ширина 10/2¹⁴≈0.0006104: любой конец находится от ответа не дальше этой ширины в точной арифметике. Средняя точка даёт границу ошибки вдвое меньше. Количество знаков после запятой само по себе не доказывает требуемую точность.

Теперь границы ограничивают вещественный ответ: left ≤ ответ ≤ right, правая граница заведомо допустима. Вместо целого left=mid+1 используем left=mid: прибавление единицы потеряло бы возможные дробные ответы. Если mid допустим, по-прежнему уменьшаем right до mid. Для ответа на самой левой границе left тоже может быть допустим.

В точной арифметике каждый двоичный шаг уменьшает ширину интервала вдвое. Если исходные границы L и R известны, можно заранее вычислить число шагов, достаточное для требуемой абсолютной ошибки ε.

Из (R−L)/2ᵏ ≤ ε получаем k ≥ log₂((R−L)/ε). Например, для начальной ширины 10⁹ и ε = 10⁻⁶ теоретически достаточно 50 шагов. В модели ниже видно, как быстро сужается интервал.

Реальные float и f64 имеют конечную точность. На больших значениях соседние представимые числа могут отстоять друг от друга больше нужной абсолютной ошибки; при многократном сужении середина может совпасть с границей. Фиксированное число итераций предотвращает бесконечный цикл, но не устраняет ошибку самой проверки.

Сверяйтесь с условием задачи: абсолютная ошибка ограничивает расстояние до ответа, относительная — расстояние в масштабе его величины. Если требуется допустимое значение параметра, возвращайте проверенную правую границу. Число знаков после запятой при выводе должно сохранять уже полученную точность, а не подменять её.

До сих пор поиск держался на переходе монотонного условия. Иногда такой проверки не видно, зато известна форма функции стоимости. Тогда применяется другой приём с отдельным условием корректности — тернарный поиск.

У функции f(x)=(x−1)²+1 на [−3,3] значения 17,5,1,5 в точках −3,−1,1,3: слева от 1 функция убывает, справа растёт. Две внутренние точки позволяют понять, с какой стороны минимума лежит более дорогая часть. Сначала рассмотрите рисунок и переключите функцию на две впадины.

Пусть функция сначала строго убывает, затем строго возрастает; между этими участками может быть плоская область глобального минимума. Например, f(x) = (x−3)²+2 имеет единственный минимум при x = 3. Мы умеем вычислять f, но не используем её производную.

Унимодальная функция (Unimodal function) — Для поиска минимума — функция, которая сначала не возрастает, затем не убывает. В стандартном тернарном шаблоне ниже дополнительно требуем строгое убывание и возрастание вне области глобального минимума.

Возьмём две внутренние точки m₁ = l+(r−l)/3 и m₂ = r−(r−l)/3. Если f(m₁) < f(m₂), минимум не может быть правее m₂: иначе на всём этом участке функция ещё убывала бы. При обратном неравенстве отбрасываем левую треть. Для указанной формы функции при равенстве можно оставить среднюю часть; сохранение одной из двух соседних частей тоже оставляет хотя бы один минимум.

repeat K times:
    m1 = l + (r-l)/3
    m2 = r − (r-l)/3
    if f(m1) <= f(m2): r = m2
    else: l = m1
return (l+r)/2

Каждый шаг сохраняет хотя бы один минимум и оставляет не больше 2/3 предыдущей ширины. Для достижения абсолютной точности ε требуется O(log((R−L)/ε)) шагов. Если вычисление f стоит O(n), эту стоимость нужно умножить на число шагов и учесть два вычисления за шаг.

Слова «сначала не возрастает, затем не убывает» без дополнительных оговорок недостаточны для стандартной обработки равенства: плоский участок выше минимума может скрывать направление спуска. В рассматриваемом шаблоне требуем строгий ход вне области глобального минимума. Унимодальность необходимо доказать по условию задачи, а не заключить по нескольким точкам графика.

Для целочисленного аргумента удобнее остановиться, когда осталось несколько кандидатов, и перебрать их. Если же можно надёжно проверять знак изменения f(mid+1)−f(mid), часто подходит двоичный поиск по этому знаку. Выбор определяется тем, какое свойство функции удалось доказать.

def minimum_value(u: float) -> float:
    def f(x: float) -> float: return (x-u)**2+1
    left, right = -4.0, 6.0
    for _ in range(100):
        m1 = left + (right-left)/3
        m2 = right - (right-left)/3
        if f(m1) <= f(m2): right = m2
        else: left = m1
    return f((left+right)/2)

print(f"{minimum_value(1.4):.6f}")

fn minimum_value(u: f64) -> f64 {
    let f=|x:f64| (x-u)*(x-u)+1.0;
    let (mut left,mut right)=(-4.0,6.0);
    for _ in 0..100 {
        let m1=left+(right-left)/3.0;
        let m2=right-(right-left)/3.0;
        if f(m1)<=f(m2) { right=m2; } else { left=m1; }
    }
    f((left+right)/2.0)
}

fn main() { println!("{:.6}",minimum_value(1.4)); }

1.000000

Двоичный и тернарный поиск похожи сужением интервала, но сохраняют разные утверждения: первый — положение перехода предиката, второй — наличие минимума. Сведём эти условия в общую схему выбора метода и проверки реализации.

Перед написанием поиска сформулируйте, что означает ответ. Для массива это может быть первая позиция ≥ x, для задачи оптимизации — минимальный допустимый параметр, для функции — точка минимума. Разные формулировки требуют разных условий, даже если код везде содержит две границы и середину.

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

Наконец, посчитайте не только число шагов, но и стоимость каждого. q запросов в готовом массиве дают O(q log n). Линейная проверка в поиске по ответу даёт O(n log R). Вещественный поиск зависит от исходного диапазона и требуемой ошибки, а не от количества цифр, которые удобно напечатать.

left, right = 0, len(a)
while left <= right:
    mid = (left + right) // 2
    # читаем a[mid]

После справочника применим эту схему к числовым ограничениям и задачам для тренировки. Цель практики — уметь самостоятельно получить предикат и инвариант, а затем выбрать подходящий шаблон поиска.

Справочник собирает определения из разобранных разделов. Используйте поиск, если нужно восстановить термин; затем переходите к оценке ограничений и задачам для самостоятельного решения.

Общий справочник всех лекций ↗

Найдено: 13 из 13

Перейдём от доказательства поиска к бюджету операций. Для целого ответа отдельно оценим ширину пространства R и стоимость одной проверки C. Общая оценка — O(C log(R + 1)). В уже готовом массиве R определяется числом позиций, а C = O(1); при поиске по ответу проверка может быть значительно дороже.

Когда число до миллиарда не требует миллиарда шагов

Для целой границы в диапазоне до 10⁹ достаточно около 30 сужений. Если каждый раз проверяется n = 200 000 объектов, это около 6 миллионов обработок объектов. Но ввод n элементов уже стоит Ω(n); получить их из файла за O(log n) невозможно.

При n = q = 100 000 одна сортировка и q запросов дают O(n log n + q log n), а повторный линейный поиск — до 10¹⁰ сравнений. После сортировки по диапазону цен уже не нужно перебирать весь возможный бюджет.

Правая граница и переполнение

В задаче упаковки прямоугольников грубая граница max(w,h)·n может достигать 10¹⁸, а произведение числа строк и столбцов — быть ещё больше. В Rust выбирайте широкий промежуточный тип или сравнение через деление. Беззнаковое left = −1 не выражает фиктивную границу; используйте знаковый тип либо шаблон [left,right).

Вещественный ответ

Из начальной ширины W и требуемой ширины ε следует k ≥ log₂(W/ε). Это рассуждение в точной арифметике; машинная погрешность проверки добавляет отдельные ограничения. Для задачи о встрече при положительных скоростях проверка стоит O(n), а 100 итераций при 60 000 участниках — порядка 6 миллионов обработок интервалов.

Тернарный поиск требует унимодальности. Если функция считается за O(n), каждое из двух вычислений учитывается в бюджете. На целой оси сужайте до нескольких кандидатов и проверяйте их явно; не ожидайте, что вещественное округление даст точный целый минимум.

Разминка перед внешними задачами

Напишите поиск точного значения, границу и подсчёт повторов. Черновики и зачёт общие с проверками глав; откройте подсказки по одной после своей попытки.

def binary_search(a, x):
	# Напишите решение
	pass

def lower_bound(a, x):
	# Напишите решение здесь
	pass

def count_occurrences(a, x):
	# Напишите решение
	pass

Основное применение и испытание

После разминки решите Search Insert Position и Sqrt(x), затем Interesting Drink и Koko Eating Bananas. Задачу, соединяющую вещественный поиск и проверку пересечения, оставьте как дополнительное испытание.

Примените разобранные приёмы самостоятельно. Для каждой задачи сначала сформулируйте требования к ответу и предложите простое решение. Затем подставьте максимальные ограничения, оцените время и память и решите, какое улучшение требуется. Подсказки с идеей и оценкой раскрываются отдельно.

Уровни задают порядок практики в курсе, а не единую шкалу платформ. Если уровень отличается от отметки LeetCode, это указано в карточке. Для Codeforces используется оценка курса.