O(log n) или O(n)? Разбор алгоритмов поиска для собеседований и практики / Хабр

Привет, Хабр! В 2006 году Джошуа Блох, автор "Effective Java" и один из создателей Java Collections Framework, опубликовал разбор бага в бинарном поиске JDK, который сидел в коде почти десять лет. Проблема оказалась в вычислении среднего индекса: (left + right) / 2 переполнялось на больших массивах. Бинарный поиск — один из первых алгоритмов, которые учат на курсах, и всё равно ошибка пряталась в стандартной библиотеке.

На собеседованиях задачи на поиск спрашивают постоянно. В продакшене разница между O(n) и O(log n) — это разница между секундами и миллисекундами на десяти миллионах записей.

В этой статье мы разберём четыре подхода:

линейный поиск
бинарный (с вариантами границ)
экспоненциальный
с использованием хеш-таблицы

и обсудим:

пограничные случаи
сравнительную таблицу
практическую задачу с LeetCode

Все примеры напишем на Python, каждый фрагмент можно запустить отдельно (чтобы побенчить, например).

Постановка задачи

Формально задача поиска формулируется так: дана коллекция элементов (чаще всего массив) arr и целевое значение target. Требуется определить, присутствует ли target в коллекции, и вернуть его индекс. Если элемент отсутствует, вернуть -1 или None. Коллекция может быть отсортированной или нет, статической или динамической.

Где это встречается на практике:

E-commerce: поиск товара по артикулу на складе. Дан массив всех артикулов (SKU - Stock Keeping Unit) - это миллионы записей. Например:

arr = [..., "1234-A-B", "2345-B-C", ..., "34567-C-D-E", ...], target = "34567-C-D-E".
Ожидается индекс позиции товара или -1, если отсутствует.

Fintech: проверка, была ли уже обработана транзакция с заданным ID. Массив ID отсортирован по времени:

arr = [73451002, 73451005, ..., 99814321], target = 81563444. Результат — индекс или -1.

Масштаб данных имеет значение:

Размер массива	Пример	Линейный поиск (сравнений)	Бинарный поиск (сравнений)
Маленький (30)	ученики в классе
Средний (5k)	песни в медиатеке
Большой (200k)	жители среднего города
Огромный (10M)	абоненты мобильного оператора

Для 10 миллионов элементов линейный поиск в худшем случае делает 10 миллионов сравнений, что может занять секунды, в то время как бинарный справится за доли миллисекунды.

Основной технический разбор

Линейный поиск (Sequential Search)

Линейный поиск подходит для любой коллекции (отсортированной или нет). Он последовательно сравнивает каждый элемент с искомым.

Шаги алгоритма:

Инициализировать индекс i = 0.
Пока i < len(arr), выполнять:
1. Если arr[i] == target, вернуть i.
2. Увеличить i на 1.
Если цикл завершился, вернуть None (или -1).

Реализация на Python:

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Анализ сложности:

Время: худший и средний случай O(n), лучший (элемент первый) O(1).
Память: O(1).

Бинарный поиск (Binary Search)

Бинарный поиск применяется только к отсортированным коллекциям. Он делит текущий интервал пополам и отбрасывает ту половину, в которой заведомо нет искомого элемента.

Шаги (итеративная версия):

Установить левую границу left = 0, правую right = len(arr) - 1.
Пока left <= right:
1. Вычислить средний индекс: mid = left + (right - left) // 2*.
2. Сравнить arr[mid] с target.
  - Если arr[mid] == target, вернуть mid.
  - Если arr[mid] < target, присвоить left = mid + 1.
  - Иначе присвоить right = mid - 1.
Если цикл завершился, элемент не найден — вернуть -1.

Защита от переполнения:* формула mid = left + (right - left) // 2 вместо (left + right) // 2 исключает переполнение при больших индексах в языках с фиксированной разрядностью (например, C++, Java..). В великом и могучем Питоне переполнения нет, однако, на собеседованиях важно показать, что Вы об этом знаете.

Важно: стандартный (классический) бинарный поиск не гарантирует, какой из дубликатов будет найден. Если нужно первое или последнее вхождение, используют модификации lower_bound и upper_bound. В случае upper_bound, если быть точным, ищется первая позиция, при вставке на которую элемента, большего искомого, не нарушается отсортированность массива.

"""Классический бинарный поиск. Возвращает индекс любого вхождения target или -1"""
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2 # В Python нет переполнения
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

"""Возвращает первый индекс, где target может быть вставлен (левая граница)."""
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left


"""Возвращает первый индекс, где элемент больше target (правая граница)"""
def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Пример
sorted_arr = [1, 3, 3, 5, 7, 9]

print(binary_search(sorted_arr, 5))  
# 3

print(lower_bound(sorted_arr, 3))  
# 1

print(upper_bound(sorted_arr, 3))  
# 3

Анализ сложности:

Время: O(log n) во всех случаях.
Память: O(1) для итеративной версии.

Экспоненциальный поиск (Exponential Search)

Экспоненциальный поиск предназначен для отсортированных массивов, размер которых может быть неизвестен (например, бесконечный поток) или когда искомый элемент находится близко к началу. Сначала он находит диапазон, где может находиться элемент, экспоненциально увеличивая границу, а затем выполняет бинарный поиск на этом диапазоне.

Шаги алгоритма:

Если массив пуст, вернуть -1.
Если arr[0] == target, вернуть 0.
Инициализировать bound = 1.
Пока bound < len(arr) и arr[bound] < target, умножить bound на 2 (расширяем границу).
Выполнить бинарный поиск на интервале [bound // 2, min(bound, len(arr)-1)].

Реализация на Python:

def exponential_search(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0

    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2

    # Бинарный поиск на суженном интервале
    left = bound // 2
    right = min(bound, len(arr) - 1)
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Пример
big_arr = list(range(1_000_000))

print(exponential_search(big_arr, 123456))  
# 123456

Анализ сложности:

Время: O(log i), где i — индекс искомого элемента, в худшем случае O(log n).
Память: O(1).

Поиск с помощью хеш-таблицы (Hash Table Search)

Хеш-таблицы обеспечивают константный в среднем доступ к элементам по ключу. В Python встроенные типы set и dict реализуют хеш-таблицы.

Шаги (при использовании set):

Построить множество из элементов коллекции (или поддерживать его динамически).
Проверить target in set.

Реализация на Python:

"""Проверяет наличие target в коллекции за O(1) в среднем."""
def hash_search_set(arr, target):
    s = set(arr)  # O(n) на построение
    return target in s

def hash_search_dict(pairs, key):
    """Поиск значения по ключу в словаре."""
    d = dict(pairs)
    return d.get(key)

# Пример
nums = [10, 20, 30, 40]

print(hash_search_set(nums, 30)) 
# True

pairs = [("a", 1), ("b", 2)]

print(hash_search_dict(pairs, "b"))
# 2

Анализ сложности:

Время: в среднем O(1), в худшем (при множественных коллизиях) O(n).
Память: O(n) для хранения хеш-таблицы.

Чек-лист: когда какой алгоритм использовать

Выбор алгоритма поиска зависит от структуры данных и самого технического задания. Основываясь на своём опыте, собрал краткое руководство, которое нетрудно держать в голове:

Массив отсортирован?
- Нет → если массив маленький (N < 100) или поиск выполняется редко, используйте линейный поиск. В противном случае рассмотрите сортировку с последующим бинарным поиском (если множество поисков) или переход к другим структурам (хеш-таблицы).
- Да → переходим к пункту 2.
Массив статический (редко меняется)?
- Да → бинарный поиск (или его вариации).
- Нет → частые вставки/удаления: используйте хеш-таблицы (если порядок не важен). Формально тут ещё есть сбалансированные деревья (set/map в C++, SortedList в Python), но лично мне за всю практику в учёбе и мобильной разработке не приходилось писать их руками — хватало хеш-таблиц.
Размер массива неизвестен или потоковый? → экспоненциальный поиск.
Требуется ли константное время вставки и поиска? → хеш-таблица (но учтите затраты памяти и отсутствие порядка).

Сравнительная таблица

Алгоритм	Время (среднее)	Время (худшее)	Требования	Рекомендуемые сценарии
Линейный поиск			Любая коллекция	Малые объёмы, неотсортированные данные, однократный поиск
Бинарный поиск	$O(log\ n)$	$O(log\ n)$	Отсортированная коллекция	Статические отсортированные массивы, частые поиски
Экспоненциальный поиск	$O(log\ i)$	$O(log\ n)$	Отсортированная коллекция	Неограниченные/потоковые данные, элемент близок к началу
Хеш-таблица			Хешируемые ключи, доп. память	Частые поиски/вставки, порядок не важен

* - среднее время для хеш-таблиц верно при условии хорошей хеш-функции и низкого коэффициента заполнения. То есть, на практике для dict/set в Питоне это справедливо, но формально - с оговоркой.

Есть ещё интерполяционный поиск, который не был включён в таблицу. Основная идея: вместо того чтобы всегда делить массив пополам, он прикидывает, где примерно должен быть элемент. Примерно так же мы ищем слово в бумажном словаре — «щ» ищем ближе к концу, а не открываем на середине. На равномерных данных это даёт O(log log n). Если Вы хотите полноценный разбор — пишите в комментариях, и мы соберём для Вас материал.

Для более явной демонстрации эффективности того или иного алгоритма всегда нужно держать в голове следующий график:

Сравнение роста числа операций для разных классов сложности (источник: bigocheatsheet.com)

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

Пограничные случаи

Реализации поисковых алгоритмов должны корректно обрабатывать нетривиальные ситуации:

Пустой массив – функции обязаны возвращать «специальное значение». В нашем коде это учтено: возвращается -1 или None.
Дубликаты – классический бинарный поиск может вернуть любой из дубликатов. Если требуется первое или последнее вхождение, используйте lower_bound/upper_bound. Важно: в production-коде недетерминированное поведение считается багом, если не оговорено иное xD.
Переполнение при вычислении среднего индекса – в языках с фиксированной разрядностью (C++, Java) выражение (left + right) // 2 может вызвать переполнение. Всегда применяйте безопасную формулу: left + (right - left) // 2. В Python целые числа неограничены, но привычка писать так полезна как для кросс-языковой переносимости, так и для переносимости собесов.
Числа с плавающей точкой – прямое сравнение arr[mid] == target ненадёжно из-за погрешностей. Используйте сравнение с допуском: abs(arr[mid] - target) < eps.
Элемент отсутствует – важно определить, что возвращать: -1, None или бросать исключение. В наших примерах используется -1 или None. Также проверяйте случаи, когда target меньше минимального или больше максимального элемента — алгоритмы должны корректно возвращать «не найдено».
Массив из одного элемента – частный случай, который часто выявляет ошибки в граничных условиях. Наши реализации проходят его (например, binary_search([42], 42) вернёт 0, binary_search([42], 100) вернёт -1).
Отрицательные индексы, большие значения – убедитесь, что границы никогда не выходят за допустимый диапазон. В lower_bound/upper_bound используется полуинтервал [0, len(arr)), что исключает обращение к несуществующим элементам.

Практическая задача: поиск первого и последнего вхождения

Условие (LeetCode, Medium): Дан отсортированный массив целых чисел nums и целевое значение target. Найдите начальную и конечную позицию target в массиве. Если target не найден, вернуть [-1, -1]. Сложность должна быть O(log n).

nums = [5,7,7,8,8,10], target = 8 → [3,4]
nums = [5,7,7,8,8,10], target = 6 → [-1,-1]

Решение с использованием lower_bound и upper_bound:

"""Возвращает [первый_индекс, последний_индекс] или [-1, -1]."""
def search_range(nums, target):
    left_idx = lower_bound(nums, target)

    if left_idx == len(nums) or nums[left_idx] != target:
        return [-1, -1]

    right_idx = upper_bound(nums, target) - 1
    return [left_idx, right_idx]

# Пример
print(search_range([5, 7, 7, 8, 8, 10], 8))
# [3, 4]

print(search_range([5, 7, 7, 8, 8, 10], 6))
# [-1, -1]

Объяснение: lower_bound находит первый индекс, где target может быть вставлен (и фактически первый индекс target, если он есть). Проверяем, что индекс в пределах массива и элемент действительно равен target. Затем upper_bound находит первый индекс элемента, большего чем target; вычитаем 1, чтобы получить последнее вхождение. Сложность — два бинарных поиска, то есть O(log n).

Итого

Четыре алгоритма — линейный, бинарный (с вариациями), экспоненциальный и хеш-таблицы — закрывают большинство задач на поиск, которые встречаются на собеседованиях и в рабочем коде.

Что стоит запомнить:

O(n) vs O(log n) — не теоретическая мелочь. На миллионах записей это разница между «всё летает» и «пользователи жалуются».
Лучшего алгоритма не существует. Данные отсортированы и не меняются — выбирайте бинарный поиск. Часто вставляете и удаляете — хеш-таблица. Маленький массив — используйте линейный.
Дьявол в деталях: переполнение mid, дубликаты, пустой массив. Именно на этих мелочах получают WA (Wrong Answer) на последних тестах и ловят баги в проде (Джошуа Блох не зря был упомянут в самом начале).
Бинарный поиск — это не только про массивы. Тот же приём работает везде, где есть монотонность: поиск по ответу, подбор параметра, бинарный поиск по времени.

Пользуясь случаем, хотел бы поделиться ссылкой на свой аккаунт на Stepik. Буду рад комментариям и лайкам под этой статьёй.