Двоичный поиск по пространству ответов
Рассматривайте непрерывный диапазон ответов как пространство поиска и решайте задачи minimum-time-to-complete-jobs и capacity-to-ship-packages
«Двоичный поиск по пространству ответов» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Двоичный поиск по пространству ответов
Большинство людей знают двоичный поиск как способ найти значение в отсортированном массиве. Но двоичный поиск становится ещё мощнее, если применять его к пространству возможных ответов. Вместо поиска в массиве выполняется поиск в числовом диапазоне — например, «какое минимальное количество дней потребуется, чтобы отправить все посылки?» — а с помощью проверочной функции определяется, допустим ли рассматриваемый ответ.
Этот метод позволяет преобразовать многие задачи оптимизации со сложностью O(n²) или выше в задачи со сложностью O(n log(max_answer)).
Шаблон поиска по пространству ответов
Шаблон состоит из трёх компонентов. Сначала определите диапазон поиска [lo, hi], охватывающий все допустимые ответы. Затем напишите проверку допустимости can_achieve(mid), которая возвращает True, если значение mid достижимо. После этого выполните двоичный поиск в диапазоне [lo, hi]: если can_achieve(mid) возвращает истину, двигайтесь к меньшему (или большему) ответу; в противном случае двигайтесь в другом направлении.
Ключевое свойство: функция допустимости должна быть монотонной — как только некоторый ответ становится допустимым, все значения за его пределами также допустимы (или все меньшие значения недопустимы).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultПример: вместимость для отправки посылок
LeetCode 1011 «Вместимость для отправки посылок за D дней»: для заданного списка весов и D дней найдите минимальную вместимость, необходимую для отправки всех посылок по порядку за D дней. Ответ находится в диапазоне [max(weights), sum(weights)]. Вместимость допустима, если жадная имитация позволяет отправить все посылки за D дней. Двоичный поиск по диапазону вместимости даёт время O(n log(sum)).
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Пример: поедание бананов Коко
LeetCode 875 «Поедание бананов Коко»: Коко может съедать K бананов в час; она хочет съесть H куч ровно за H часов, минимизируя K. Диапазон поиска — [1, max(piles)]. Проверка: при скорости K общее количество часов равно сумме значений ceil(pile/K), и оно должно быть <= H. Мы выполняем двоичный поиск наименьшего K, удовлетворяющего этому условию.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Пример: минимальное число дней для составления букетов
LeetCode 1482 «Минимальное число дней для составления m букетов»: необходимо составить m букетов, каждый из k расположенных подряд распустившихся цветов. Цветок i распускается в день bloomDay[i]. Выполните двоичный поиск по дню: диапазон — от 1 до максимального значения bloomDay. Проверка допустимости подсчитывает идущие подряд распустившиеся цветы и определяет, можно ли составить m букетов. Свойство монотонности: если подходит день d, то подходит и день d+1.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Определение диапазона поиска
Правильный выбор диапазона [lo, hi] имеет решающее значение. lo должен быть минимально возможным ответом (например, минимальным элементом, 1 или 0), а hi — максимально возможным ответом (например, суммой всех элементов, максимальным элементом или n). Слишком маленькое значение hi исключит допустимые ответы; слишком большое значение не создаёт проблемы, поскольку двоичный поиск всё равно сойдётся за O(log(hi - lo)) шагов.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')Максимизация и минимизация: направление имеет значение
У двоичного поиска по пространству ответов есть два варианта. Минимизация ответа: если проверка пройдена, ищите меньшее значение (hi = mid); если проверка не пройдена, ищите большее (lo = mid + 1). Максимизация ответа: если проверка пройдена, ищите большее значение (lo = mid + 1, сохраняя mid как кандидат); если проверка не пройдена, ищите меньшее (hi = mid - 1). Перед написанием кода всегда уточняйте, в каком направлении ведётся поиск.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Выделение минимального числа страниц (классическая задача)
Даны n книг с массивом страниц и k студентов. Распределите книги непрерывными отрезками так, чтобы минимизировать максимальное число страниц, которое читает один студент. Выполните двоичный поиск по ответу (минимально возможному максимуму). Проверка допустимости жадно распределяет книги студентам: если добавление книги превысило бы текущий максимум, книга передаётся новому студенту. Если требуется <= k студентов, такой максимум достижим.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Анализ сложности поиска по пространству ответов
Временная сложность составляет O(n × log(диапазона)), где n — стоимость проверки допустимости (обычно линейного прохода), а размер диапазона равен hi - lo. Например, если сумма страниц равна 10⁹, а проверка допустимости выполняется за O(n), общее время составляет O(n log 10⁹) ≈ O(30n), что значительно лучше полного перебора за O(n²).
Пространственная сложность самого двоичного поиска равна O(1), не считая памяти, которую использует проверка допустимости.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')k-й наименьший элемент в отсортированной матрице
LeetCode 378 «k-й наименьший элемент в отсортированной матрице»: каждая строка и каждый столбец матрицы n×n отсортированы. Выполните двоичный поиск по значению ответа в диапазоне [matrix[0][0], matrix[n-1][n-1]]. Проверка допустимости подсчитывает элементы, меньшие или равные середине диапазона, используя указатель, начинающийся в левом нижнем углу, за O(n). Найдите наименьшее значение, для которого хотя бы k элементов меньше или равны ему.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Распознавание задач поиска по пространству ответов
Задачи, подходящие для двоичного поиска по пространству ответов, имеют общие признаки: в условии требуется найти минимальное или максимальное значение, ответ находится в ограниченном числовом диапазоне, а увеличение или уменьшение кандидатного ответа монотонно улучшает или ухудшает его допустимость. Классические формулировки включают «минимально возможный максимум», «не более k операций» и «за d дней».
Заметив эти признаки, сразу определите нижнюю и верхнюю границы, напишите функцию проверки допустимости и примените шаблон. Такой структурированный подход редко подводит на собеседованиях.
Быстрая проверка
Проверьте, насколько хорошо Вы понимаете изложенные в этом уроке концепции структур данных и алгоритмов — подготовки к техническим собеседованиям.
Итоги урока
В этом уроке Вы узнали: двоичный поиск по пространству ответов применяется, когда функция проверки допустимости монотонна на числовом диапазоне, шаблон выполняет поиск в диапазоне [lo, hi] и использует проверку достижимости can_achieve, чтобы вдвое уменьшать пространство поиска, а общая сложность составляет O(n log(range)), где n — стоимость одной проверки допустимости. Далее мы перейдём к связным спискам и классу узлов.
Часто задаваемые вопросы
Урок «Двоичный поиск по пространству ответов» бесплатный?
Да — полный текст урока «Двоичный поиск по пространству ответов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Двоичный поиск по пространству ответов»?
Рассматривайте непрерывный диапазон ответов как пространство поиска и решайте задачи minimum-time-to-complete-jobs и capacity-to-ship-packages Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Двоичный поиск по пространству ответов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Классический двоичный поиск: левый, правый, средний
- Двоичный поиск в повёрнутых и неотсортированных массивах
- Нижняя и верхняя границы
- Двоичный поиск по пространству ответов