Мы уже обсуждали двоичный поиск в массиве. Оказывается, массив тут необязателен: такая же идея отлично применяется и в более общем случае.

Задача

Для начала рассмотрим такую задачу: у нас есть $n$ стойл, в которые необходимо расставить $k$ коров, $1 < k < n$.

Требуется расставить коров так, чтобы минимальное расстояние между коровами было максимальным.

Идея

Для начала рассмотрим другую задачу: пусть нам дано $x$ и сказано, что мы не можем ставить коров так, чтобы расстояние между ними было меньше $x$, и требуется узнать, сможем ли мы расставить коров.

Эта задача легко решается за $O(n)$ жадным алгоритмом: мы ставим корову в самое левое стойло, потом в первое стойло на расстоянии хотя бы $x$ и так далее, пока не дойдём до конца массива.

Последнее замечание: если мы смогли расставить коров нужным образом при каком-нибудь $x$, то при любом меньшем точно сможем. Таким образом, функция check(x), которой назовём описанный выше алгоритм, монотонна: сначала она возвращает $1$, а после определённой точки - $0$. Для решения исходной задачи нам достаточно найти эту точку: это и будет ответом на задачу.

Делать это мы будем как раз с помощью бинпоиска: ясно, что $check(0) = 1$ и $check(s + 1) = 0$, где $s$ - расстояние от первого стойла до последнего. Обозначим $l = 0, r = s + 1$ и будем делить отрезок $[l, r]$ пополам, пока он делится, смотреть на середину $m$ и если $check(m) = 1$, то присваивать $l = m$, а иначе - $r = m$.

Реализация

Здесь a - упорядоченный массив стойл.

def check(x):
    cur = 0
    cnt = 0
    while cur < len(a) and cnt < k:
        cnt += 1
        prev = cur
        while cur < len(a) and a[cur] - a[prev] < x:
            cur += 1
    return cnt == k


l = 0
r = a[-1] - a[0] + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m
print(l)

Корректность алгоритма

Наш алгоритм имеет инвариант: $check(l) = 1$, $check(r) = 0$. Когда он завершится, мы будем иметь $l + 1 = r$, значит, $l$ и будет последней точкой, в которой $check$ равна $1$.

Асимптотика

Всего будет сделано $O(log n)$ итераций бинпоиска. Каждая итерация имеет сложность $O(n)$ из-за функции $check$. Итоговая асимптотика - $O(nlogn)$.

Обобщение

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

Про границы

В этой задаче нам было легко определить исходные границы $l$ и $r$, но так бывает не всегда. Иногда точная оценка на границы выходит очень сложной. Распространённая ошибка - писать какие-то сложные формулы или, ещё хуже, писать дополнительный алгоритм для поиска этих самых начальных границ.

На самом деле ошибка даже в 2 раза в установке какой-нибудь границы ничего не меняет, ведь увеличит число итераций всего лишь на $1$. Как правило, можно даже ставить ограничения максимальными теоретически возможными, то есть, например, $2\cdot 10^{18}$, потому что это почти самое большое число, которое можно хранить в $64$-битном целочисленном типе данных. Мы всё равно сделаем лишь около $64$ итераций, чего обычно вполне достаточно.

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