Поиск данных — одна из фундаментальных задач в программировании. Будь то поиск элемента в массиве, кратчайшего пути в графе или подстроки в тексте — эффективность решения напрямую зависит от выбранного алгоритма. В этой статье мы последовательно разберём более 20 алгоритмов поиска,
разделив их на категории: линейные структуры, графы и деревья, строки,
специализированные методы. Для каждого алгоритма дано краткое описание
идеи, асимптотическая сложность и готовый к использованию код на Go.
Часть 1. Поиск в линейных структурах (массивы, срезы)
1. Линейный (последовательный) поиск
Суть:
просматриваем каждый элемент по порядку, пока не найдём искомый или не
дойдём до конца. Работает на любых неотсортированных данных.
Сложность: O(n) в худшем и среднем случае.
Пример на Go:
go
package main
import "fmt"
// LinearSearch ищет первое вхождение target в slice.
// Возвращает индекс или -1, если не найден.
func LinearSearch(slice []int, target int) int {
for i, v := range slice {
if v == target {
return i
}
}
return -1
}
func main() {
data := []int{5, 2, 9, 1, 7, 3}
fmt.Println(LinearSearch(data, 7)) // 4
fmt.Println(LinearSearch(data, 8)) // -1
}
2. Бинарный поиск
Суть: работает только на отсортированном массиве. На каждом шаге сравниваем искомый элемент со средним; если он меньше — ищем в левой половине, иначе — в правой.
Сложность: O(log n).
Пример на Go (итеративная версия):
go
func BinarySearch(sorted []int, target int) int {
left, right := 0, len(sorted)-1
for left <= right {
mid := left + (right-left)/2 // защита от переполнения
if sorted[mid] == target {
return mid
}
if sorted[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
// использование:
// sorted := []int{1, 2, 3, 5, 7, 9}
// fmt.Println(BinarySearch(sorted, 5)) // 3
3. Тернарный поиск
Суть: для поиска максимума/минимума унимодальной
функции (или элемента в отсортированном массиве, но бинарный обычно
эффективнее). Делим интервал на три части и отбрасываем одну из крайних.
Сложность: O(log n) с основанием 3, но с большей константой, чем бинарный.
Пример для поиска элемента в отсортированном массиве (неоптимально, но демонстрирует идею):
go
func TernarySearch(sorted []int, target int) int {
left, right := 0, len(sorted)-1
for left <= right {
if left == right {
if sorted[left] == target {
return left
}
return -1
}
mid1 := left + (right-left)/3
mid2 := right - (right-left)/3
if sorted[mid1] == target {
return mid1
}
if sorted[mid2] == target {
return mid2
}
if target < sorted[mid1] {
right = mid1 - 1
} else if target > sorted[mid2] {
left = mid2 + 1
} else {
left = mid1 + 1
right = mid2 - 1
}
}
return -1
}
4. Интерполяционный поиск
Суть: улучшение бинарного поиска для равномерно распределённых данных. Позиция предполагается по формуле:
pos = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]).
Если распределение близко к равномерному, работает быстрее бинарного.
Сложность: в среднем O(log log n), в худшем O(n).
Пример на Go:
go
func InterpolationSearch(sorted []int, target int) int {
left, right := 0, len(sorted)-1
for left <= right && target >= sorted[left] && target <= sorted[right] {
if left == right {
if sorted[left] == target {
return left
}
return -1
}
// Интерполяционная формула
pos := left + (target-sorted[left])*(right-left)/(sorted[right]-sorted[left])
if pos < left || pos > right {
return -1
}
if sorted[pos] == target {
return pos
}
if sorted[pos] < target {
left = pos + 1
} else {
right = pos - 1
}
}
return -1
}
5. Экспоненциальный поиск
Суть:
сначала определяем диапазон, где может находиться элемент, увеличивая
индекс экспоненциально (1, 2, 4, 8…), затем на этом диапазоне запускаем
бинарный поиск. Отлично подходит для бесконечных или очень длинных
массивов.
Сложность: O(log n).
Пример:
go
func ExponentialSearch(sorted []int, target int) int {
n := len(sorted)
if n == 0 {
return -1
}
if sorted[0] == target {
return 0
}
bound := 1
for bound < n && sorted[bound] < target {
bound *= 2
}
// Бинарный поиск на отрезке [bound/2, min(bound, n-1)]
left := bound / 2
right := min(bound, n-1)
for left <= right {
mid := left + (right-left)/2
if sorted[mid] == target {
return mid
}
if sorted[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
6. Поиск прыжками (Jump Search)
Суть: для отсортированного массива. Двигаемся блоками фиксированного размера √n, затем внутри последнего блока выполняем линейный поиск. Оптимальный размер блока — √n.
Сложность: O(√n).
Пример:
go
import "math"
func JumpSearch(sorted []int, target int) int {
n := len(sorted)
step := int(math.Sqrt(float64(n)))
prev := 0
for sorted[min(step, n)-1] < target {
prev = step
step += int(math.Sqrt(float64(n)))
if prev >= n {
return -1
}
}
// Линейный поиск в блоке [prev, step]
for i := prev; i < min(step, n); i++ {
if sorted[i] == target {
return i
}
}
return -1
}
7. Поиск Фибоначчи
Суть:
использует числа Фибоначчи для деления массива, не требует
деления/умножения (только сложение/вычитание). Эффективен на платформах,
где деление дорого. Алгоритм ищет элемент в отсортированном массиве.
Сложность: O(log n).
Пример:
go
func FibonacciSearch(sorted []int, target int) int {
n := len(sorted)
fib2 := 0 // (m-2)-е число Фибоначчи
fib1 := 1 // (m-1)-е число Фибоначчи
fib := fib1 + fib2 // m-е число Фибоначчи
for fib < n {
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
}
offset := -1
for fib > 1 {
i := min(offset+fib2, n-1)
if sorted[i] < target {
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = i
} else if sorted[i] > target {
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
} else {
return i
}
}
if fib1 == 1 && sorted[offset+1] == target {
return offset + 1
}
return -1
}
8. Поиск с помощью хеш-таблицы
Суть:
предварительно строим хеш-таблицу (map), где ключ — значение элемента,
значение — его позиция. Поиск выполняется за O(1) в среднем. Требует
дополнительной памяти.
Пример:
go
type HashSetIndex struct {
m map[int]int
}
func NewHashIndex(slice []int) *HashSetIndex {
m := make(map[int]int)
for i, v := range slice {
m[v] = i
}
return &HashSetIndex{m: m}
}
func (h *HashSetIndex) Search(target int) (int, bool) {
idx, ok := h.m[target]
return idx, ok
}
Часть 2. Поиск в графах и деревьях
9. Поиск в глубину (DFS)
Суть:
рекурсивный обход графа: заходим в вершину, затем рекурсивно обходим
всех её непосещённых соседей. Используется для проверки связности,
поиска пути (не кратчайшего), топологической сортировки.
Сложность: O(V + E) для списков смежности.
Пример на Go для графа (список смежности):
go
type Graph struct {
adj map[int][]int
}
func NewGraph() *Graph {
return &Graph{adj: make(map[int][]int)}
}
func (g *Graph) AddEdge(u, v int) {
g.adj[u] = append(g.adj[u], v)
g.adj[v] = append(g.adj[v], u) // для неориентированного
}
func (g *Graph) DFS(start int, target int) bool {
visited := make(map[int]bool)
return g.dfsRecursive(start, target, visited)
}
func (g *Graph) dfsRecursive(v, target int, visited map[int]bool) bool {
if v == target {
return true
}
visited[v] = true
for _, neighbor := range g.adj[v] {
if !visited[neighbor] {
if g.dfsRecursive(neighbor, target, visited) {
return true
}
}
}
return false
}
10. Поиск в ширину (BFS)
Суть: обход графа по уровням с помощью очереди. Гарантирует нахождение кратчайшего пути в невзвешенном графе.
Сложность: O(V + E).
Пример (поиск кратчайшего расстояния):
go
func (g *Graph) BFS(start, target int) int {
if start == target {
return 0
}
visited := make(map[int]bool)
queue := []int{start}
dist := make(map[int]int)
dist[start] = 0
visited[start] = true
for len(queue) > 0 {
v := queue[0]
queue = queue[1:]
for _, neighbor := range g.adj[v] {
if !visited[neighbor] {
visited[neighbor] = true
dist[neighbor] = dist[v] + 1
if neighbor == target {
return dist[neighbor]
}
queue = append(queue, neighbor)
}
}
}
return -1 // нет пути
}
11. Алгоритм Дейкстры
Суть: поиск кратчайших путей от источника до всех вершин во взвешенном графе с неотрицательными весами. Использует приоритетную очередь.
Сложность: O((V + E) log V) с кучей.
Пример на Go (с использованием container/heap):
go
import (
"container/heap"
)
type Item struct {
node int
dist int
}
type PriorityQueue []Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
x := old[n-1]
*pq = old[:n-1]
return x
}
func Dijkstra(graph map[int][][2]int, start, target int) int {
dist := make(map[int]int)
for v := range graph {
dist[v] = int(^uint(0) >> 1) // MaxInt
}
dist[start] = 0
pq := &PriorityQueue{}
heap.Push(pq, Item{start, 0})
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
if cur.node == target {
return cur.dist
}
if cur.dist > dist[cur.node] {
continue
}
for _, edge := range graph[cur.node] {
neighbor, weight := edge[0], edge[1]
newDist := cur.dist + weight
if newDist < dist[neighbor] {
dist[neighbor] = newDist
heap.Push(pq, Item{neighbor, newDist})
}
}
}
return -1
}
12. A* (A-star)
Суть: эвристический алгоритм поиска кратчайшего пути. Использует функцию f(n) = g(n) + h(n), где g — стоимость пути от старта, h — эвристическая оценка до цели. Обычно применяется в играх и геоинформатике.
Сложность: зависит от эвристики, в худшем случае экспоненциальна.
Пример (упрощённо, на сетке): реализация громоздка, поэтому приведём лишь концептуальную структуру. В реальном проекте используйте готовые библиотеки.
go
// Предполагаем, что есть функция heuristic(a, b) и граф
// Основа — приоритетная очередь, как в Дейкстре, но с приоритетом f = g + h.
13. Алгоритм Беллмана — Форда
Суть: находит кратчайшие пути в графе с любыми весами (включая отрицательные), обнаруживает отрицательные циклы. Работает медленнее Дейкстры.
Сложность: O(V * E).
Пример:
go
func BellmanFord(edges [][3]int, V, start, target int) int {
dist := make([]int, V)
for i := range dist {
dist[i] = int(1e9)
}
dist[start] = 0
for i := 0; i < V-1; i++ {
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
if dist[u] != int(1e9) && dist[u]+w < dist[v] {
dist[v] = dist[u] + w
}
}
}
// Проверка на отрицательный цикл (опущена для краткости)
if dist[target] == int(1e9) {
return -1
}
return dist[target]
}
14. Поиск с возвратом (Backtracking)
Суть:
систематический перебор вариантов с откатом при обнаружении тупика.
Используется в задачах комбинаторного поиска (ферзи, судоку, поиск пути в
лабиринте).
Пример (поиск пути в лабиринте):
go
func findPath(maze [][]int, x, y, targetX, targetY int, visited [][]bool) bool {
if x == targetX && y == targetY {
return true
}
if x < 0 || y < 0 || x >= len(maze) || y >= len(maze[0]) || maze[x][y] == 1 || visited[x][y] {
return false
}
visited[x][y] = true
// пробуем 4 направления
if findPath(maze, x+1, y, targetX, targetY, visited) ||
findPath(maze, x-1, y, targetX, targetY, visited) ||
findPath(maze, x, y+1, targetX, targetY, visited) ||
findPath(maze, x, y-1, targetX, targetY, visited) {
return true
}
visited[x][y] = false // возврат
return false
}
Часть 3. Поиск подстроки в строке
15. Наивный алгоритм
Суть: сравниваем шаблон с каждым возможным окном в тексте. Самый простой, но медленный.
Сложность: O(n * m) в худшем случае.
Пример:
go
func NaiveSearch(text, pattern string) int {
n, m := len(text), len(pattern)
for i := 0; i <= n-m; i++ {
j := 0
for j < m && text[i+j] == pattern[j] {
j++
}
if j == m {
return i
}
}
return -1
}
16. Алгоритм Кнута — Морриса — Пратта (KMP)
Суть:
предварительно строит префикс-функцию, которая позволяет не возвращать
указатель в тексте назад. Эффективен для поиска в длинных текстах.
Сложность: O(n + m).
Пример:
go
func KMPSearch(text, pattern string) int {
n, m := len(text), len(pattern)
if m == 0 {
return 0
}
// построение префикс-функции
prefix := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && pattern[i] != pattern[j] {
j = prefix[j-1]
}
if pattern[i] == pattern[j] {
j++
}
prefix[i] = j
}
// поиск
for i, j := 0, 0; i < n; i++ {
for j > 0 && text[i] != pattern[j] {
j = prefix[j-1]
}
if text[i] == pattern[j] {
j++
}
if j == m {
return i - m + 1
}
}
return -1
}
17. Алгоритм Бойера — Мура
Суть:
использует эвристики «плохого символа» и «хорошего суффикса», сдвигая
шаблон на максимально возможное расстояние. Один из быстрейших для
текстов на естественном языке.
Сложность: в среднем O(n/m), в худшем O(n*m).
Пример (упрощённая версия — только эвристика плохого символа):
go
func BoyerMooreSearch(text, pattern string) int {
n, m := len(text), len(pattern)
if m == 0 {
return 0
}
// таблица плохих символов
badChar := make(map[byte]int)
for i := 0; i < m; i++ {
badChar[pattern[i]] = i
}
s := 0
for s <= n-m {
j := m - 1
for j >= 0 && pattern[j] == text[s+j] {
j--
}
if j < 0 {
return s
}
// сдвиг
if idx, ok := badChar[text[s+j]]; ok {
s += max(1, j-idx)
} else {
s += j + 1
}
}
return -1
}
func max(a, b int) int {
if a > b { return a }
return b
}
18. Алгоритм Рабина — Карпа
Суть:
использует хеширование. Вычисляет хеш шаблона и хеши для каждого окна
текста; при совпадении хешей проверяет символы. Хорош для поиска
множества шаблонов.
Сложность: в среднем O(n + m), в худшем O(n*m).
Пример:
go
func RabinKarp(text, pattern string) int {
n, m := len(text), len(pattern)
if m == 0 || m > n {
return -1
}
const prime = 101
const d = 256
h := 1
for i := 0; i < m-1; i++ {
h = (h * d) % prime
}
p := 0 // хеш шаблона
t := 0 // хеш текущего окна
for i := 0; i < m; i++ {
p = (d*p + int(pattern[i])) % prime
t = (d*t + int(text[i])) % prime
}
for i := 0; i <= n-m; i++ {
if p == t {
// проверка посимвольно
match := true
for j := 0; j < m; j++ {
if text[i+j] != pattern[j] {
match = false
break
}
}
if match {
return i
}
}
if i < n-m {
t = (d*(t-int(text[i])*h) + int(text[i+m])) % prime
if t < 0 {
t += prime
}
}
}
return -1
}
19. Алгоритм Ахо — Корасик
Суть:
поиск множества подстрок одновременно. Строит автомат из набора
шаблонов (бор + суффиксные ссылки). Применяется в системах фильтрации
слов, антивирусах.
Сложность: O(n + сумма длин всех шаблонов + количество совпадений).
Пример (основная структура):
go
type AhoNode struct {
next [26]int
fail int
out bool
}
func BuildAho(patterns []string) []AhoNode {
// реализация требует объёмного кода, здесь приведена идея
// Создаётся корневой узел, для каждого шаблона добавляются символы,
// затем строятся fail-ссылки BFS-ом.
return nil
}
// Функция поиска: проходит по тексту, переходит по автомату,
// при out == true находит совпадение.
Часть 4. Поиск в деревьях поиска
20. Бинарное дерево поиска (BST)
Суть: каждый узел имеет ключ; все ключи левого поддерева меньше узла, правого — больше. Поиск идёт рекурсивно.
Сложность: O(log n) в среднем, O(n) в худшем.
Пример структуры и метода поиска:
go
type TreeNode struct {
Value int
Left *TreeNode
Right *TreeNode
}
func (node *TreeNode) Search(target int) bool {
if node == nil {
return false
}
if node.Value == target {
return true
}
if target < node.Value {
return node.Left.Search(target)
}
return node.Right.Search(target)
}
21. Сбалансированные деревья (AVL, красно-чёрное)
Суть:
автоматически поддерживают высоту дерева ~log n. Поиск аналогичен BST,
но операции вставки/удаления сложнее (балансировка). В Go стандартная
библиотека не предоставляет готовых реализаций, но можно использовать
сторонние пакеты или реализовать самостоятельно.
Пример поиска в AVL (поиск не отличается от BST): тот же код Search, что и выше.
22. B-деревья
Суть:
используются в базах данных и файловых системах; узел может содержать
множество ключей и дочерних узлов. Поиск — последовательный проход по
ключам внутри узла и спуск по соответствующему указателю.
Сложность: O(log n) с большим основанием.
Пример (упрощённая структура):
go
type BTreeNode struct {
keys []int
children []*BTreeNode
leaf bool
}
func (node *BTreeNode) Search(target int) bool {
i := 0
for i < len(node.keys) && target > node.keys[i] {
i++
}
if i < len(node.keys) && target == node.keys[i] {
return true
}
if node.leaf {
return false
}
return node.children[i].Search(target)
}
23. Trie (префиксное дерево)
Суть: хранит строки по символам, позволяет быстро искать по префиксу. Используется в автодополнении, словарях.
Сложность: O(L), где L — длина строки.
Пример:
go
type TrieNode struct {
children [26]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{}}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
node.children[idx] = &TrieNode{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
return false
}
node = node.children[idx]
}
return node.isEnd
}
Часть 5. Специализированные алгоритмы поиска
24. Быстрый выбор (Quickselect)
Суть:
находит k-й по порядку элемент (медиану, минимум, максимум) без полной
сортировки. Основан на идее быстрой сортировки (разбиение Хоара).
Сложность: в среднем O(n), в худшем O(n²).
Пример (поиск k-го наименьшего):
go
func Quickselect(arr []int, k int) int {
if len(arr) == 1 {
return arr[0]
}
pivot := arr[0]
left := make([]int, 0)
right := make([]int, 0)
for i := 1; i < len(arr); i++ {
if arr[i] < pivot {
left = append(left, arr[i])
} else {
right = append(right, arr[i])
}
}
if k < len(left) {
return Quickselect(left, k)
} else if k == len(left) {
return pivot
} else {
return Quickselect(right, k-len(left)-1)
}
}
25. Поиск в отсортированной матрице
Суть: матрица, в которой строки и столбцы отсортированы по возрастанию. Можно начать с правого верхнего угла и двигаться вниз/влево.
Сложность: O(n + m).
Пример:
go
func SearchInSortedMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
row, col := 0, len(matrix[0])-1
for row < len(matrix) && col >= 0 {
if matrix[row][col] == target {
return true
}
if matrix[row][col] < target {
row++
} else {
col--
}
}
return false
}
Заключение
Мы рассмотрели более двух десятков алгоритмов поиска — от простого
линейного перебора до сложных эвристических методов, таких как A*.
Каждый алгоритм имеет свою область применения: бинарный поиск идеален
для статических отсортированных данных, хеш-таблицы — для быстрого
доступа по ключу, KMP и Бойер-Мур — для работы с текстами, а BFS и
Дейкстра — для графов. В реальных проектах важно оценивать не только
асимптотическую сложность, но и константу, объём дополнительной памяти,
характер данных.
Все приведённые примеры на Go являются рабочими фрагментами, которые можно использовать как основу для собственных реализаций. Go предоставляет
простой синтаксис, но требует внимательности при работе со срезами и
указателями, особенно в графовых алгоритмах.
Надеемся, эта статья поможет вам увереннее выбирать подходящий алгоритм поиска для ваших задач. Успешного кодинга!