Поисковая стратегия разделяй и властвуй

Мы уже знаем, что алгоритмы поиска делятся на две большие категории.

• Полный перебор: реализуется через обход структуры данных, временная сложность равна \(O(n)\) .
• Адаптивный поиск: использует особую организацию данных или априорную информацию, временная сложность может достигать \(O(\log n)\) и даже \(O(1)\) .

На практике алгоритмы поиска с временной сложностью \(O(\log n)\) обычно реализуются на основе стратегии «разделяй и властвуй», например двоичный поиск и деревья.

• На каждом шаге двоичный поиск раскладывает задачу (поиск целевого элемента в массиве) на более мелкую задачу (поиск целевого элемента в одной половине массива), и этот процесс продолжается, пока массив не станет пустым или пока не будет найден целевой элемент.
• Деревья являются типичными представителями идей «разделяй и властвуй». В таких структурах данных, как двоичное дерево поиска, AVL-дерево и куча, временная сложность различных операций равна \(O(\log n)\) .

Стратегия «разделяй и властвуй» для двоичного поиска выглядит следующим образом.

• Задача раскладывается на части: двоичный поиск рекурсивно разбивает исходную задачу (поиск в массиве) на подзадачу (поиск в одной половине массива), и это достигается сравнением среднего элемента с целевым значением.
• Подзадачи независимы: в двоичном поиске на каждом шаге обрабатывается только одна подзадача, и она не зависит от других подзадач.
• Решения подзадач не нужно объединять: двоичный поиск нацелен на поиск конкретного элемента, поэтому объединять решения подзадач не требуется. Как только подзадача решена, одновременно считается решенной и исходная задача.

Иными словами, стратегия «разделяй и властвуй» повышает эффективность поиска потому, что при полном переборе за один шаг удается исключить только один вариант, тогда как при поиске на основе «разделяй и властвуй» за один шаг можно исключить половину вариантов.

Реализация двоичного поиска на основе «разделяй и властвуй»

В предыдущих главах двоичный поиск реализовывался через итерацию. Теперь реализуем его с помощью стратегии «разделяй и властвуй», то есть через рекурсию.

Question

Дан отсортированный массив nums длины \(n\) , в котором все элементы уникальны. Найдите элемент target .

С точки зрения стратегии «разделяй и властвуй» обозначим подзадачу, соответствующую интервалу поиска \([i, j]\) , через \(f(i, j)\) .

Начиная с исходной задачи \(f(0, n-1)\) , выполняем двоичный поиск по следующим шагам.

1. Вычислить середину \(m\) интервала поиска \([i, j]\) и с ее помощью исключить половину интервала.
2. Рекурсивно решить подзадачу вдвое меньшего размера. Это может быть либо \(f(i, m-1)\) , либо \(f(m+1, j)\) .
3. Повторять шаг 1. и шаг 2. , пока не будет найден target или пока интервал не станет пустым.

На рисунке ниже показан процесс применения стратегии «разделяй и властвуй» для поиска элемента \(6\) в массиве.

В реализации кода мы объявляем рекурсивную функцию dfs() для решения задачи \(f(i, j)\) :

[file]{binary_search_recur}-[class]{}-[func]{binary_search}