Классический двоичный поиск: левый, правый, средний
Реализуйте двоичный поиск итеративно и рекурсивно, разберитесь с границами lo/hi и проверьте корректность на граничных входных данных
«Классический двоичный поиск: левый, правый, средний» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Почему важен двоичный поиск
Двоичный поиск сокращает линейный просмотр O(n) до O(log n), деля область поиска пополам на каждом шаге. В массиве из миллиона элементов линейный просмотр требует до 1 000 000 сравнений, а двоичному поиску нужно не более 20. Благодаря этой эффективности двоичный поиск — один из алгоритмов, которые чаще всего проверяют на собеседованиях по программированию.
Основная идея заключается в том, что отсортированный массив позволяет после одного сравнения полностью отбросить одну из половин оставшихся данных.
Схема левой, средней и правой границ
Двоичный поиск использует три указателя на индексы: lo (левая граница), hi (правая граница) и mid (середина). На каждой итерации вычислите mid = (lo + hi) // 2 и сравните искомое значение с arr[mid]. Если искомое значение меньше, переместите границу: hi = mid - 1; если больше — lo = mid + 1; если равно — значение найдено.
Цикл продолжается, пока выполняется условие lo <= hi. Если цикл завершился, не найдя искомое значение, верните -1.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1Как избежать переполнения целого числа при вычислении mid
Выражение mid = (lo + hi) // 2 может вызвать переполнение целого числа в языках с целыми числами фиксированной разрядности (Java, C++). Целые числа Python имеют произвольную точность, поэтому переполнение невозможно, но на собеседовании от Вас всё же ожидают знания безопасной альтернативы: mid = lo + (hi - lo) // 2.
Эта форма вычисляет ту же середину, но прибавляет к lo только половину расстояния, вместо того чтобы сначала складывать оба указателя. Упоминание этого приёма на собеседовании показывает, что Вы учитываете низкоуровневые аспекты.
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # TrueГраницы с включением и без включения
Одна из самых сложных частей двоичного поиска — решить, указывает ли hi на последний допустимый индекс (граница включается, hi = len(arr) - 1) или на позицию сразу за концом (граница не включается, hi = len(arr)). Разные соглашения требуют разных условий цикла и обновлений границ.
Для границ с включением используйте while lo <= hi и обновляйте hi = mid - 1. Для границ без включения используйте while lo < hi и обновляйте hi = mid. Смешение соглашений — самый частый источник ошибок в реализациях двоичного поиска.
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2Рекурсивный двоичный поиск
Двоичный поиск можно записать рекурсивно, передавая обновлённые границы lo и hi через стек вызовов. Каждый рекурсивный вызов вдвое уменьшает область поиска, поэтому глубина равна O(log n). Базовый случай наступает, когда lo > hi (значение не найдено) или arr[mid] == target (значение найдено).
В рабочем коде предпочтительна итеративная версия, поскольку она не создаёт накладных расходов на кадры стека, но рекурсивная версия яснее показывает структуру «разделяй и властвуй» на доске.
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4Граничные случаи: пустой массив, один элемент
Надёжный двоичный поиск должен обрабатывать граничные случаи без сбоев. Три самых распространённых случая: пустой массив (цикл не выполняется и корректно возвращается -1), массив из одного элемента (mid равен lo и hi, достаточно одного сравнения) и искомые значения вне диапазона (lo в итоге становится больше hi и возвращается -1).
Всегда проверяйте реализацию на этих входных данных, прежде чем переходить к дополнительным вопросам на собеседовании.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)Временная и пространственная сложность
Временная сложность двоичного поиска равна O(log n), поскольку каждое сравнение вдвое уменьшает область поиска. После k сравнений остаётся область размера n/2^k; поиск завершается, когда её размер достигает 1, поэтому k = log₂ n.
Пространственная сложность равна O(1) для итеративной версии (используются только три целочисленные переменные) и O(log n) для рекурсивной версии из-за глубины стека вызовов. На собеседовании всегда называйте обе оценки и предпочитайте итеративную форму, если пространство ограничено.
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')Поиск точного совпадения и границы
Классический двоичный поиск возвращает любой индекс, по которому находится искомое значение. Но во многих задачах на собеседованиях требуется найти первое или последнее вхождение искомого значения. В таких случаях после совпадения нужно продолжать поиск: не возвращайте результат сразу, а сужайте границу и двигайтесь дальше.
При поиске первого вхождения после обнаружения arr[mid] == target сохраните mid как возможный ответ и установите hi = mid - 1. Для последнего вхождения установите lo = mid + 1.
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1Использование модуля bisect в Python
Стандартная библиотека Python предоставляет bisect.bisect_left(arr, x) и bisect.bisect_right(arr, x) для готового к использованию двоичного поиска. bisect_left возвращает самый левый индекс, куда можно вставить x, сохранив сортировку массива; фактически он находит первую позицию, для которой выполняется arr[i] >= x.
На собеседовании Вам могут разрешить использовать bisect; всегда сначала уточняйте это. Однако всё равно необходимо понимать, как модуль работает внутри (это двоичный поиск со сложностью O(log n)).
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # TrueРаспространённые ошибки двоичного поиска
Три ошибки вызывают большинство проблем с двоичным поиском на собеседованиях. Во-первых, неверное условие цикла: использование < вместо <= при включительных границах приводит к пропуску последнего оставшегося элемента. Во-вторых, неправильное обновление границы: если забыть +1 или -1, при lo == hi возникнет бесконечный цикл. В-третьих, работа с неотсортированным массивом: двоичный поиск корректен только для отсортированных данных.
Перед написанием любого двоичного поиска проговорите вслух: «Массив отсортирован, мои границы включительные, а цикл выполняется, пока lo <= hi».
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)Советы для собеседования по двоичному поиску
Когда Вы видите задачу с отсортированным массивом, монотонно возрастающей функцией или областью поиска, которую можно делить пополам, сразу рассмотрите двоичный поиск. На собеседовании проговаривайте ход своих мыслей: «Поскольку массив отсортирован, при каждом сравнении я могу отбросить половину элементов, получив сложность O(log n)».
Всегда проверяйте решение как минимум на трёх входных данных: значении в начале, значении в конце и отсутствующем значении. Если заранее назвать сложность — «время O(log n), пространство O(1)», — это показывает прочные базовые знания.
Быстрая проверка
Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованиям по программированию» из этого урока.
Повторение урока
В этом уроке Вы узнали, что двоичный поиск на каждом шаге вдвое уменьшает область поиска и работает за O(log n), что соглашение с включительными границами использует lo <= hi с обновлениями lo = mid+1 и hi = mid-1, а также что для поиска первого или последнего вхождения после совпадения нужно продолжать поиск, а не возвращать результат сразу. Далее мы рассмотрим, как двоичный поиск применяется к циклически сдвинутым и неотсортированным массивам.
Часто задаваемые вопросы
Урок «Классический двоичный поиск: левый, правый, средний» бесплатный?
Да — полный текст урока «Классический двоичный поиск: левый, правый, средний» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Классический двоичный поиск: левый, правый, средний»?
Реализуйте двоичный поиск итеративно и рекурсивно, разберитесь с границами lo/hi и проверьте корректность на граничных входных данных Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Классический двоичный поиск: левый, правый, средний»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Классический двоичный поиск: левый, правый, средний
- Двоичный поиск в повёрнутых и неотсортированных массивах
- Нижняя и верхняя границы
- Двоичный поиск по пространству ответов