Алгоритм поиска — метод нахождения элемента в данных. Бинарный поиск находит нужное из миллиона элементов за 20 шагов; Дейкстра строит кратчайший маршрут на карте.
💻Алгоритмы поиска
Бинарный поиск — O(log n): из 1 млн элементов за 20 шагов. Линейный — O(n): 1 млн шагов. Дейкстра и A* находят кратчайший путь в графах. Основа баз данных и навигаторов.
Загрузка карты...
Поиск — самая частая операция в программировании
Каждый раз, когда ты ищешь контакт в телефоне, товар на маркетплейсе или маршрут в навигаторе — работает алгоритм поиска. Разница между O(n) и O(log n) на миллиарде элементов — это разница между секундой и 30 годами.
Линейный поиск: просто, но медленно
Самый очевидный подход: проверяем элементы по одному. Нашли — возвращаем. Не нашли — идём дальше. O(n) — время растёт линейно с размером массива.
Когда использовать: маленький массив, неотсортированный массив, единственный вариант. В реальных системах почти не применяется для больших данных.
Бинарный поиск: O(log n) — магия пополам
Работает только на отсортированном массиве. Берём средний элемент. Если он больше искомого — ищем в левой половине. Если меньше — в правой. Повторяем.
Каждый шаг отбрасывает половину оставшихся элементов. Из 1 000 000 элементов — нужно максимум 20 шагов (log₂(1 000 000) ≈ 20). Это и есть O(log n).
Используется: словари, базы данных с B-деревьями, бинарные деревья поиска (BST), поиск в отсортированных списках.
Сравнение алгоритмов поиска
| Алгоритм | Сложность | Структура | Применение |
|---|---|---|---|
| Линейный | O(n) | Любой массив | Маленькие данные |
| Бинарный | O(log n) | Отсортированный массив | Словари, БД |
| BFS | O(V+E) | Граф | Кратчайший путь (без весов) |
| DFS | O(V+E) | Граф/дерево | Обход, топосортировка |
| Дейкстра | O((V+E) log V) | Граф с весами | GPS, сети |
| A* | O((V+E) log V) | Граф с весами + эвристика | Игры, навигаторы |
Сравнительная таблица: анализ различий
Шагов для поиска в 1 млн элементов
Максимум шагов
Поиск в графах: BFS и DFS
Массив — линейная структура. Но мир часто устроен как граф: узлы и рёбра. Социальная сеть, карта метро, зависимости пакетов.
BFS (поиск в ширину) — исследуем все ближайшие узлы, потом их соседей, и так далее. Кольцами. Гарантирует нахождение кратчайшего пути (по числу рёбер). Сложность O(V + E), где V — вершины, E — рёбра. Используется: социальные сети («6 рукопожатий»), веб-краулеры.
DFS (поиск в глубину) — идём как можно глубже по одному пути, потом возвращаемся и пробуем другой. Рекурсивен. O(V + E). Используется: обход деревьев, топологическая сортировка, поиск компонент связности.
Дейкстра: кратчайший путь с весами
BFS находит кратчайший путь по числу рёбер. Но если рёбра имеют вес (расстояние, стоимость, время) — нужен алгоритм Дейкстры (1956, нидерландский учёный Эдсгер Дейкстра).
Принцип: всегда обрабатываем ближайший необработанный узел. Обновляем расстояния до соседей. Повторяем. O((V + E) log V) с приоритетной очередью.
Используется: GPS-навигация, маршрутизация в сетях (OSPF-протокол), логистика.
A*: Дейкстра с интуицией
A* (1968) улучшает Дейкстру, добавляя эвристику — оценку расстояния до цели. Вместо исследования всех направлений A* «чувствует», в какую сторону двигаться.
Эвристика должна быть допустимой (не переоценивать расстояние). Для карт — евклидово расстояние. A* на реальных картах в разы быстрее чистого Дейкстры. Используется: навигаторы, AI в играх (поиск пути персонажей).
❓Часто задаваемые вопросы
Алгоритм отбрасывает половину массива на каждом шаге. Это работает только если знаешь: всё слева меньше, всё справа больше.