Поиск в списке: линейный и бинарный

Найти элемент в списке можно по-разному. Разберём два базовых способа и поймём, почему один бывает намного быстрее.

Линейный поиск

Самый простой способ: идём по списку с начала и проверяем каждый элемент, пока не найдём нужный. Работает всегда, но на большом списке медленный — в худшем случае просмотрим все элементы.

nums = [4, 8, 15, 16]
print(15 in nums)   # Python сам делает линейный поиск -> True

Бинарный поиск

Если список уже отсортирован, можно искать умнее: смотрим в середину, и если искомое меньше — отбрасываем правую половину, если больше — левую. Каждый шаг вдвое сокращает область поиска, поэтому даже в огромном списке хватает нескольких шагов.

Когда какой

Список маленький или не отсортирован — линейный поиск проще и достаточно. Список большой и отсортирован — бинарный поиск в разы быстрее. Понимание этой разницы — первый шаг к теме сложности алгоритмов.

Частые вопросы

Почему бинарный требует сортировки? Он опирается на порядок, чтобы отбрасывать половину; без сортировки это не работает.

Что использовать новичку? Для простых задач — оператор in (линейный поиск); бинарный — когда важна скорость на больших данных.