Поиск элемента в массиве, оценка сложности алгоритмов O(n) и O(log n)
Поиск как одна из самых частых операций обработки данных
Поиск нужного значения — одна из самых часто выполняемых операций в программах, работающих с данными: поиск товара по названию в интернет-магазине, поиск контакта по имени в телефонной книге, поиск нужной записи в базе данных. От того, насколько быстро выполняется поиск, напрямую зависит быстродействие всей программы, особенно если поиск выполняется многократно на больших объёмах данных — поэтому выбору и оценке алгоритма поиска уделяют отдельное внимание уже на этапе проектирования программы.
Задача поиска элемента в массиве
Поиском называют задачу определения того, содержится ли заданное значение (искомый элемент, ключ) в массиве, и если содержится — нахождения его индекса (позиции). Способ решения этой задачи существенно зависит от того, упорядочен ли массив. Если массив не отсортирован, единственный надёжный способ — просмотреть все его элементы по очереди (линейный поиск); если же массив отсортирован, можно применить гораздо более быстрый алгоритм — бинарный (двоичный) поиск.
Линейный поиск
Линейный (последовательный) поиск — простейший алгоритм: элементы массива просматриваются по очереди, начиная с первого, пока не будет найден элемент, равный искомому, либо пока не закончится массив. Такой алгоритм работает для любого массива — отсортированного или нет.
def linear_search(a, target):
for i in range(len(a)):
if a[i] == target:
return i # индекс найденного элемента
return -1 # элемент не найден
a = [8, 3, 15, 6, 42, 9, 21]
print(linear_search(a, 42)) # 4
print(linear_search(a, 100)) # -1
В худшем случае (искомого элемента нет в массиве, либо он находится в самом конце) линейному поиску требуется просмотреть все n элементов массива, поэтому его временная сложность оценивается как линейная.
Подсчёт числа сравнений при линейном поиске
Полезно уметь считать не только сам факт нахождения элемента, но и число выполненных операций сравнения — это напрямую иллюстрирует понятие временной сложности алгоритма на конкретном примере.
def linear_search_with_count(a, target):
comparisons = 0
for i in range(len(a)):
comparisons += 1
if a[i] == target:
return i, comparisons
return -1, comparisons
a = [8, 3, 15, 6, 42, 9, 21]
index, count = linear_search_with_count(a, 6)
print(f'Найден на позиции {index}, сравнений сделано: {count}')
Бинарный (двоичный) поиск: идея
Бинарный поиск применяется только к отсортированному массиву и работает по принципу «разделяй и властвуй»: сравнивая искомое значение со средним элементом массива, алгоритм за одно сравнение отбрасывает сразу половину массива, в которой искомого элемента заведомо быть не может. Затем поиск повторяется в оставшейся половине — и так далее, пока диапазон поиска не сузится до одного элемента или не окажется пустым.
На каждом шаге рассматриваются три индекса: left — левая граница текущего диапазона поиска, right — правая граница, mid — индекс среднего элемента диапазона. Если a[mid] равен искомому значению — элемент найден. Если a[mid] меньше искомого значения, искать нужно в правой половине (left = mid + 1); если a[mid] больше искомого — в левой половине (right = mid − 1).
Алгоритм бинарного поиска (итеративная реализация)
def binary_search(a, target):
left, right = 0, len(a) — 1
while left <= right:
mid = (left + right) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
left = mid + 1
else:
right = mid — 1
return -1 # элемент не найден
a = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91] # массив ОТСОРТИРОВАН
print(binary_search(a, 23)) # 5
print(binary_search(a, 100)) # -1
Пример работы бинарного поиска по шагам
Разберём поиск числа 23 в массиве a = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91] (индексы от 0 до 10). Изначально left=0, right=10. Шаг 1: mid=(0+10)//2=5, a[5]=23 — искомый элемент найден сразу же за одно сравнение. Рассмотрим менее удачный случай — поиск числа 45. Шаг 1: left=0, right=10, mid=5, a[5]=23<45, значит left=6. Шаг 2: left=6, right=10, mid=8, a[8]=56>45, значит right=7. Шаг 3: left=6, right=7, mid=6, a[6]=38<45, значит left=7. Шаг 4: left=7, right=7, mid=7, a[7]=45 — найдено. Всего потребовалось 4 сравнения вместо 8, которые сделал бы линейный поиск.
Оценка сложности бинарного поиска
На каждом шаге бинарного поиска диапазон возможных позиций искомого элемента уменьшается ровно вдвое. Поэтому число шагов, необходимых для сужения диапазона из n элементов до одного, равно количеству раз, которое нужно разделить n на 2, чтобы получить 1, — то есть двоичному логарифму от n.
Разница между O(n) и O(log₂n) огромна на больших массивах: для массива из миллиона элементов линейному поиску в худшем случае потребуется до миллиона сравнений, тогда как бинарному поиску — не более log₂1 000 000 ≈ 20 сравнений.
Рекурсивная реализация бинарного поиска
Так как на каждом шаге бинарный поиск сводит задачу поиска в массиве к точно такой же задаче поиска в подмассиве вдвое меньшего размера, его естественно реализовать и рекурсивно; базовый случай — пустой диапазон поиска (left > right) или совпадение со средним элементом.
def binary_search_recursive(a, target, left, right):
if left > right:
return -1 # базовый случай: элемент не найден
mid = (left + right) // 2
if a[mid] == target:
return mid # базовый случай: элемент найден
elif a[mid] < target:
return binary_search_recursive(a, target, mid + 1, right)
else:
return binary_search_recursive(a, target, left, mid — 1)
a = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]
print(binary_search_recursive(a, 45, 0, len(a) — 1)) # 7
Поиск всех вхождений элемента
Линейный поиск легко обобщить на случай, когда искомое значение может встречаться в массиве несколько раз и требуется найти не только первое, но и все его вхождения: в этом случае цикл не прерывается оператором return при первом же совпадении, а продолжает просмотр всего массива, накапливая найденные индексы в отдельном списке.
def find_all(a, target):
positions = []
for i in range(len(a)):
if a[i] == target:
positions.append(i)
return positions
a = [3, 7, 3, 9, 3, 5, 3]
print(find_all(a, 3)) # [0, 2, 4, 6]
print(len(find_all(a, 3)), 'вхождений')
Обратите внимание: для бинарного поиска аналогичная задача (найти все вхождения значения в отсортированном массиве) решается сложнее — после нахождения одного вхождения нужно дополнительно «расширять» диапазон влево и вправо, проверяя соседние элементы, поскольку одинаковые значения в отсортированном массиве всегда стоят подряд.
Сравнение линейного и бинарного поиска
| Критерий | Линейный поиск | Бинарный поиск |
|---|---|---|
Требование к массиву | не требуется сортировка | массив должен быть отсортирован |
Сложность в худшем случае | O(n) | O(log₂n) |
Сравнений для n=1000 | до 1000 | до 10 |
Простота реализации | проще | требует аккуратной работы с границами |
Типичные ошибки
Главная и самая частая ошибка — применение бинарного поиска к неотсортированному массиву: алгоритм в этом случае может не найти существующий элемент или найти неверный результат, при этом не сообщив об ошибке. Вторая распространённая ошибка — неверная работа с границами диапазона: использование строгого сравнения left < right вместо left <= right приводит к тому, что не проверяется последний оставшийся элемент, а забытое обновление left = mid + 1 (вместо left = mid) — к бесконечному циклу. Также часто путают условие a[mid] < target и a[mid] > target, что приводит к сужению диапазона в неверную сторону. Наконец, для линейного поиска типичная ошибка — не предусмотреть возврат -1 (или другого признака «не найдено») в случае отсутствия элемента в массиве.
Краткий словарь терминов
Линейный поиск — последовательный просмотр всех элементов массива до нахождения искомого значения.
Бинарный (двоичный) поиск — алгоритм поиска в отсортированном массиве, на каждом шаге отбрасывающий половину диапазона поиска.
Временная сложность алгоритма — оценка того, как растёт время работы алгоритма с ростом размера входных данных.
O(n) — линейная сложность: время работы пропорционально числу элементов.
O(log₂n) — логарифмическая сложность: время работы пропорционально логарифму числа элементов.
Разделяй и властвуй — принцип построения алгоритмов, сводящий задачу к решению аналогичной задачи меньшего размера.
Заключение
Линейный и бинарный поиск демонстрируют, насколько сильно выбор алгоритма влияет на скорость решения одной и той же задачи: логарифмическая сложность бинарного поиска на больших объёмах данных даёт огромный выигрыш по сравнению с линейной сложностью, но требует предварительной сортировки массива. Вопрос о том, как эффективно упорядочить массив, если он ещё не отсортирован, рассматривается в следующей теме — алгоритмах сортировки и оценке их сложности.
