Первое True: двоичный поиск по предикату
Ищите монотонную границу да/нет
«Первое True: двоичный поиск по предикату» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Ищите границу «да» и «нет»
Во многих задачах скрыт монотонный предикат: сначала ложь, затем навсегда истина. Двоичный поиск позволяет найти первую истину даже без отсортированного массива.
# FFFFTTTT -> find first TЧто означает монотонность
Предикат является монотонным, если после перехода в истинное состояние он остаётся истинным. Именно это свойство позволяет найти границу двоичным поиском.
def ok(x):
return x * x >= targetОпределите пространство ответов
Выберите диапазон, который наверняка содержит границу. Установите low равным наименьшему кандидату, а high — значению, для которого ok наверняка истинно.
low, high = 0, 10**9Проверьте середину
Возьмите mid и вызовите ok(mid). Логический результат подскажет, какую половину оставить, точно так же, как сравнение значения при обычном двоичном поиске.
mid = (low + high) // 2
if ok(mid):
...Истина означает: возможно, есть меньшее значение
Если ok(mid) возвращает истину, mid — допустимый ответ, но может подойти и меньшее значение. Сохраните mid, установив high = mid, а не mid - 1.
if ok(mid):
high = midЛожь означает: двигайтесь выше
Если ok(mid) возвращает ложь, граница находится выше mid. Отбросьте mid и всё, что ниже, с помощью low = mid + 1.
else:
low = mid + 1Цикл, пока low меньше high
Используйте while low < high, а не условие «меньше или равно». Два указателя сойдутся на первом истинном индексе, после чего цикл завершится.
while low < high:
mid = (low + high) // 2Ответ находится в low
Когда цикл завершится, low будет равен high, и оба указателя будут указывать на первое истинное значение. Верните low как искомую границу.
return low # first x where ok(x)Почему работает high = mid
Поскольку mid может быть ответом, его нельзя пропускать. Значение high = mid сохраняет его в диапазоне и одновременно сужает диапазон, гарантируя продвижение.
high = mid # mid stays a candidateПример с целочисленным квадратным корнем
Чтобы найти наибольшее x, для которого x*x не превышает n, найдите первое истинное значение для условия x*x > n, а затем отступите на один шаг назад. Этот шаблон можно применять снова и снова.
def ok(x):
return x * x > n
# answer is found_index - 1Один шаблон для множества задач
Этот шаблон поиска первого истинного значения решает бесчисленное множество задач: поиск минимального допустимого значения, самого левого индекса или наименьшей вместимости. Освойте его один раз и применяйте повсюду.
# low<high, ok->high=mid, else low=mid+1Быстрая проверка
Определите действие, которое сохраняет кандидата.
Повторение: первое истинное значение найдено
Теперь вы умеете превращать задачу в монотонный предикат и находить границу двоичным поиском. Связка high = mid и while low < high — безопасный шаблон. 🧭
Часто задаваемые вопросы
Урок «Первое True: двоичный поиск по предикату» бесплатный?
Да — полный текст урока «Первое True: двоичный поиск по предикату» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Первое True: двоичный поиск по предикату»?
Ищите монотонную границу да/нет Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Первое True: двоичный поиск по предикату»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Классический двоичный поиск без ошибок
- bisect_left и bisect_right
- Первое True: двоичный поиск по предикату
- Двоичный поиск по ответу