0Pricing
Coding Interview Prep · Урок

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

Предположите результат и проверьте его осуществимость

«Двоичный поиск по ответу» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Предположите, затем проверьте

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

# guess X, ask: is X feasible?

Волшебное свойство

Метод работает, когда выполнимость монотонна: если значение подходит, то любое большее или меньшее значение также подходит. Именно этот порядок вы и ищете.

# feasible(X) true => feasible(X+1) true

Ограничьте диапазон ответа

Определите наименьший и наибольший возможные ответы как low и high. Для минимальной вместимости low равен одному элементу, а high — общей сумме.

low, high = max(weights), sum(weights)

Напишите проверку выполнимости

Суть метода — функция can(X), которая возвращает true, если предположение X достижимо. Обычно она работает за линейное время.

def can(cap):
    # simulate and return True/False
    ...

Пример: доставка за D дней

Имея дневную вместимость cap, жадно распределяйте элементы по дням и считайте их количество. can(cap) возвращает true, когда число дней не превышает ограничение D.

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

Ищите минимальную вместимость

Вам нужна наименьшая подходящая cap. Это поиск первого истинного значения среди вместимостей, поэтому снова используйте шаблон high = mid.

while low < high:
    mid = (low + high) // 2

Оставьте допустимую половину

Если can(mid) возвращает true, может подойти и меньшая вместимость, поэтому установите high = mid. В противном случае поднимите нижнюю границу с помощью low = mid + 1.

if can(mid):
    high = mid
else:
    low = mid + 1

Учитывайте ограничение по времени

Общая стоимость равна O(check x log range). Линейная проверка диапазона шириной в миллиард значений требует всего около 30 проверок и достаточно быстра даже при строгих ограничениях.

# log2(1e9) is about 30 iterations

Максимизируйте вместо минимизации

Чтобы найти наибольшее допустимое значение, измените логику: ищите последнее истинное значение. Увеличивайте low, когда значение допустимо, и уменьшайте high в противном случае.

if can(mid):
    low = mid
else:
    high = mid - 1

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

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

for _ in range(100):
    mid = (low + high) / 2

Распознавайте шаблон

Фразы вроде «минимум из максимумов», «максимум из минимумов» или «наименьшее подходящее k» — это сигналы для двоичного поиска по ответу. Учитесь замечать их.

# 'minimize the maximum' => search answer

Быстрая проверка

Определите, когда применим двоичный поиск по ответу.

Повторение: ищите ответ

Теперь вы умеете ограничивать ответ, писать проверку выполнимости и выполнять двоичный поиск минимума или максимума. Сложные задачи превращаются в проверку предположения. 🏆

Часто задаваемые вопросы

Урок «Двоичный поиск по ответу» бесплатный?

Да — полный текст урока «Двоичный поиск по ответу» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Двоичный поиск по ответу»?

Предположите результат и проверьте его осуществимость Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Двоичный поиск по ответу»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Классический двоичный поиск без ошибок
  2. bisect_left и bisect_right
  3. Первое True: двоичный поиск по предикату
  4. Двоичный поиск по ответу
← Назад к Coding Interview Prep