PrepBro
← Назад к вопросам

Какие знаешь алгоритмы поиска?

2.0 Middle🔥 161 комментариев
#Python Core#Архитектура и паттерны

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Какие знаешь алгоритмы поиска?

Вот основные алгоритмы поиска, которые каждый разработчик должен знать:

Поиск в массивах

Linear Search — O(n)

  • Когда: маленькие или несортированные массивы
  • Простой проход по каждому элементу

Binary Search — O(log n)

  • Когда: отсортированные данные
  • Делит массив пополам, как угадывание числа
  • Быстрейший алгоритм для сортированных данных

Jump Search — O(√n)

  • Когда: отсортированные данные, но binary недоступен
  • Прыгает на √n шагов, потом линейный поиск

Interpolation Search — O(log log n)

  • Когда: равномерно распределённые отсортированные данные
  • Угадывает позицию (как интерполяция в математике)

Ternary Search — O(log₃ n)

  • Когда: поиск максимума в унимодальном массиве (один пик)
  • Делит на 3 части вместо 2

Поиск в графах

DFS (Depth-First Search) — O(V+E)

  • Идёт в глубину по графу
  • Используется для: лабиринты, топологическая сортировка, компоненты связности
  • Реализация: рекурсия или явный стек

BFS (Breadth-First Search) — O(V+E)

  • Идёт в ширину по уровням
  • Используется для: кратчайший путь в невзвешенном графе, уровни в дереве
  • Реализация: очередь (deque)

Специальные алгоритмы

A Search*

  • Для: кратчайший путь с эвристикой (maps, игры)
  • Сложность: зависит от эвристики
  • Лучше, чем Dijkstra если есть хорошая эвристика

Dijkstra's Algorithm

  • Для: кратчайший путь в взвешенном графе
  • O((V + E) log V) с приоритетной очередью

Binary Search Tree (BST) Operations

  • Поиск в BST: O(log n) сбалансированный, O(n) худший
  • Используется в: индексах БД, системах файлов

Сравнение по времени на 1 млн элементов

АлгоритмВремя
Linear Search~0.5 сек
Binary Search~0.0001 сек
Ускорение:5000x!

Практическое правило выбора

Есть отсортированный массив?
  ДА → Binary Search ✓
  НЕТ → Отсортируй, потом Binary Search ✓

Это граф?
  Нужен кратчайший путь? → BFS ✓
  Нужно пройти все вершины? → DFS ✓

Данные равномерные и большие?
  ДА → Interpolation Search ✓

Ключевые выводы

  • Binary Search в 5000 раз быстрее Linear для больших данных
  • BFS для кратчайшего пути, DFS для обхода
  • Выбор алгоритма часто важнее оптимизации кода
  • Всегда сортируй перед binary search!