Бинарный поиск — это алгоритм поиска элемента в отсортированной последовательности, который на каждом шаге делит пространство поиска пополам. Этот метод значительно эффективнее линейного поиска, особенно для больших массивов данных.
Основные характеристики
Требование к данным: последовательность должна быть отсортирована
Принцип работы: алгоритм сравнивает искомый элемент со средним элементом массива и в зависимости от результата сравнения продолжает поиск в левой или правой половине
Эффективность: обеспечивает логарифмическую временную сложность
Сложность алгоритма
| Случай | Сложность | Описание |
|---|---|---|
| Лучший случай | O(1) | Искомый элемент находится точно в середине массива |
| Средний случай | O(log n) | Элемент находится где-то в массиве |
| Худший случай | O(log n) | Элемент отсутствует или находится на краю |
from random import randint
searching_item = 7
list_ = [randint(1,10) for i in range(10)]
list_.sort()
def searching(list_, value):
left = 0
rigth = len(list_) - 1
while left <= rigth:
mid = (left + rigth) // 2
if value == list_[mid]:
return True
elif value < list_[mid]:
rigth = mid - 1
else:
left = mid + 1
return False
print(searching(list_, searching_item))
Почему бинарный поиск эффективен?
Быстрое сокращение пространства поиска: на каждом шаге алгоритм отбрасывает половину оставшихся элементов
Предсказуемое время выполнения: даже для очень больших массивов количество шагов остается небольшим
Простота реализации: базовый алгоритм можно реализовать примерно в 10 строк кода
Ограничения бинарного поиска
Требуется предварительная сортировка данных
Не подходит для часто изменяющихся данных (из-за затрат на поддержание отсортированного состояния)
Работает только с последовательностями, поддерживающими произвольный доступ (неэффективен для связных списков)