Классический двоичный поиск без ошибок
Правильно настройте цикл с low, high и mid
«Классический двоичный поиск без ошибок» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Сократите пространство поиска вдвое
Двоичный поиск находит значение в отсортированном списке, каждый раз деля диапазон пополам. Так медленный проход за O(n) превращается в быстрый поиск за O(log n).
a = [1, 3, 5, 7, 9] # must be sortedОтсортированность — главное правило
Двоичный поиск работает только с отсортированными данными. Если список не упорядочен, сначала отсортируйте его, иначе результат будет бессмысленным и неверным.
a.sort() # ascending order requiredДве границы
Начните с двух указателей: low на индексе 0 и high на последнем индексе. Если цель присутствует, она всегда находится между ними.
low, high = 0, len(a) - 1Безопасно найдите середину
Вычисляйте mid как low + (high - low) // 2. В Python переполнение не является проблемой, но везде полезно выработать привычку использовать эту безопасную форму.
mid = low + (high - low) // 2Три исхода
Сравните a[mid] с целью. Либо вы нашли её, либо значение слишком мало, либо слишком велико. В каждом случае диапазон уменьшается по-разному.
if a[mid] == target:
return midСлишком мало — двигайтесь вправо
Если a[mid] меньше цели, ответ должен находиться правее. Переместите low на mid + 1 и отбросьте левую половину.
elif a[mid] < target:
low = mid + 1Слишком велико — двигайтесь влево
Если a[mid] больше цели, ищите в левой половине. Переместите high на mid - 1, чтобы больше не проверять mid.
else:
high = mid - 1Условие цикла
Продолжайте пока low не больше high. Когда указатели пересекутся, диапазон станет пустым, а цель будет отсутствовать.
while low <= high:
mid = low + (high - low) // 2Сообщите, что значение не найдено
Если цикл завершился без совпадения, значение отсутствует. По соглашению возвращайте -1, чтобы вызывающая сторона могла отличить успех от неудачи.
return -1 # target not in listЛовушка смещения на единицу
Классическая ошибка — забыть +1 или -1 при перемещении указателя. Если пропустить это изменение, mid будет проверяться снова и снова, что приведёт к бесконечному циклу.
low = mid + 1 # not low = midИспользуйте библиотеку, когда это возможно
Для обычной проверки принадлежности модуль Python bisect уже предоставляет поиск без ошибок. Пишите цикл вручную только тогда, когда нужна нестандартная логика.
import bisect
i = bisect.bisect_left(a, target)Быстрая проверка
Подумайте, что обеспечивает корректность цикла.
Повторение: поиск без ошибок
Теперь вы умеете задавать low и high, безопасно вычислять mid, сужать правую сторону и избегать ловушки смещения на единицу. Логарифмический поиск теперь у вас в арсенале. 🎯
Часто задаваемые вопросы
Урок «Классический двоичный поиск без ошибок» бесплатный?
Да — полный текст урока «Классический двоичный поиск без ошибок» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Классический двоичный поиск без ошибок»?
Правильно настройте цикл с low, high и mid Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Классический двоичный поиск без ошибок»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Классический двоичный поиск без ошибок
- bisect_left и bisect_right
- Первое True: двоичный поиск по предикату
- Двоичный поиск по ответу