Как найти границу, когда все "хорошие" ответы слева, а "плохие" справа
l, r = 0, n
while l < r - 1:
m = (l + r) // 2
if ok(m):
l = m
else:
r = m
# Ответ: lint l = 0, r = n, m;
while (l < r - 1) {
m = (l + r) / 2;
if (ok(m))
l = m;
else
r = m;
}
// Ответ: lЭто способ найти максимальное (или минимальное) значение, которое удовлетворяет какому-то условию, когда все меньшие значения тоже подходят, а все большие — нет. Или наоборот.
Главная идея: если мы умеем быстро проверять, подходит ли нам какое-то число, то можно не перебирать все варианты по очереди, а отсекать половину диапазона на каждом шаге.
Представьте, что у нас есть отрезок чисел от 0 до n. Про каждое число мы можем сказать "хорошее" или "плохое". Причём все хорошие числа идут подряд слева, а плохие — справа. Наша задача — найти последнее хорошее число.
На каждом шаге мы смотрим на середину m:
l = mr = mТак мы сужаем отрезок, пока между l и r не останется ни одного целого числа. Когда l и r станут соседями (r = l + 1), ответом будет l — последнее хорошее число.
Скорость работы: за один шаг мы отбрасываем половину оставшихся вариантов. Поэтому нужно всего O(log n) шагов, где n — длина отрезка.
Пусть у нас есть числа от 0 до 10. Условие: число считается "хорошим", если оно меньше 7. То есть хорошие числа: 0,1,2,3,4,5,6. Плохие: 7,8,9,10.
Нужно найти самое большое хорошее число — это 6.
Шаг 1: l=0, r=10 → середина m=5 → 5 хорошее → l=5
Шаг 2: l=5, r=10 → середина m=7 → 7 плохое → r=7
Шаг 3: l=5, r=7 → середина m=6 → 6 хорошее → l=6
Шаг 4: l=6, r=7 → между ними нет целых чисел → остановОтвет: 6
Где применяется:
Задайте диапазон и условие, чтобы найти границу: