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

В словарях все слова упорядочены. Можно воспользоваться этим свойством словаря. Вот пусть нам надо найти слово «мямлик». Откроем словарь посередине, и посмотрим на первое слово на странице. Оно начинается на букву «Н», которая идет после буквы «М» значит вторая, нижняя половина нам не нужна. Продолжаем поиск в первой, верхней половине. Снова располовиниваем половину, и смотрим на первую букву первого слова. Это буква «К». Теперь нужно отбросить уже первую половину половины, и оставить вторую половину половины.

Продолжаем этот процесс, смотрим на вторую букву слова, мы находимся внутри блока слов на букву «М», на третью и так далее, пока, наконец, не найдем наше слово.

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

У нас есть массив упорядоченных ключей $K_1, K_2, K_3, \dotsc, K_{n-1}, K_n$.

Я хочу найти в этом массиве номер ключа $K$, то есть такое $j$, что $K_j = K$.

Допустим, я сейчас нахожусь на позиции $i$ и смотрю на ключ $K_i$. Я сравниваю этот ключ $K_i$ с искомым ключом $K$. У меня три варианта:

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

Перед тем, как превратить наше рукомахание в рабочий код, надо провести некоторые манипуляции.

Для начала надо завести переменные left и right, показывающие границы поиска. В самом начале $\code{left} = 0$, а $\code{right} = n - 1$. Серединный элемент будем постоянно выбирать как $\code{middle} = \lfloor (\code{left} + \code{right}) / 2 \rfloor$, и на основе значения $K_{\code{middle}}$ будем менять или правую границу, или левую.

Все действия будем делать до тех пор, пока в границе поиска не останется один элемент. В этом случае мы просто проверим, совпадает ли он с нашей целью.

Область поиска мы каждую итерацию делим пополам. Получается, что временная сложность алгоритма $O(\log n)$.

Существует альтернативный подход к бинарному поиску — однородный бинарный поиск. Вместо хранения границ left и right он использует текущую позицию i и размер шага m, который уменьшается вдвое на каждой итерации.

Этот алгоритм особенно полезен в системах с ограниченной памятью, ведь мы используем всего $2$ переменные вместо $3$.

Последовательность шагов предсказуема, ведь шаг всегда равен $m, m/2, m/4, m/8, \dotsc$, поэтому можно создавать эффективные логические схемы.

Каждую итерацию цикла мы вынуждены вычислять новое значение $m$. Можно заранее посчитать все значения $m$, а потом многократно использовать посчитанные значения, ведь они зависят только от размера массива $n$.

Всего нам нужно хранить $\lfloor \log_2 n \rfloor + 2$ значения в таблице

Тогда на $j$-м шаге нужно брать $m = \delta[j]$

Давайте поподробнее проанализируем алгоритм и его время работы.

Для наглядности изобразим всю процедуру в виде дерева принятия решений для массива длины $15$.

Начинаем мы с самой верхушки дерева. Каждую итерацию мы сравниваем искомое значение $K$ со значением в вершине, и выбираем, куда пойти: вправо или влево. Дерево решений построено так, что левое поддерево каждой вершины меньше значения в этой вершине, а правое поддерево больше.

Количество уровней в дереве решений $\lfloor \log_2 n \rfloor + 1$. Каждую итерацию мы спускаемся вниз ровно на $1$ уровень.

Эффективность алгоритма оценивается количеством сравнений $C$. Получается, что успешный поиск при $2^{k-1} \le n < 2^k$ требует минимум $1$ и максимум $k$ сравнений, и неудачный поиск при $2^{k-1} \le n < 2^k - 1$ требует $k-1$ или $k$ сравнений.

Оценим среднее количество сравнений, предположив равномерное распределение аргументов поиска. Поиск может закончиться успешно или неудачно. Пусть $C$ — количество сравнений при успешном поиске, а $C'$ — количество сравнений при неудачном поиске.

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

Ну и можно вывести интересную связь между успешным и неудачном поиском

Глубина дерева решений $\lfloor \log_2 n \rfloor$. При этом в дереве решений заполнены все уровни, кроме, возможно, последнего. На всех уровнях, кроме последнего, всего $2^{\lfloor \log_2 n \rfloor} - 1$ элементов. На последнем уровне $n - 2^{\lfloor \log_2 n \rfloor} + 1$ элементов.

Для подсчета средней глубины элементов воспользуемся формулой

Подставляем это в формулу $\expect C = 1 + \expect(\text{глубина элемента})$, считаем и получаем

Посмотрим теперь на массив, который почти отсортирован. В нём каждый элемент находится не дальше чем на $k$ элементов от своей правильной позиции в полностью отсортированном массиве.

То есть, если элемент в отсортированном массиве должен находится на позиции $j$, то в почти отсортированном массиве он может находиться на любой позиции от $j-k$ до $j+k$.

Числа Фибоначчи могут играть такую же роль, что и степени двойки. Числа Фибоначчи позволяют разработать альтернативу бинарному поиску, где не нужно будет выполнять никаких операций, кроме сложения.

Что, если у нас нет быстрой операции деления? Или мы хотим минимизировать количество сравнений для массивов, которые не идеально укладываются в степень двойки? Здесь на помощь приходят числа Фибоначчи.

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

Пусть нам нужно искать ключ $K$ в отсортированном массиве с $n$ ключами $K_1 < K_2 < \dotsb < K_n$.

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

Найдем такое наименьшее $m \ge 0$, что $n + m$ на $1$ меньше какого-то числа Фибоначчи. То есть $n + m = F_{k+1} - 1$.

Установим начальный индекс поиска $j = F_k - m$. Это будет наш текущий индекс-указатель. Будем вычислять шаги по двум числам $p$ и $q$, которые всегда являются числами Фибоначчи. В начале $p = F_{k-1}$ и $q = F_{k-2}$.

На каждой итерации нам нужно выполнять проверку $4$ условий и совершать действия в зависимости от результата

При этом поиск завершается неудачей, если после сравнения оказалось, что $q = 0$, или, что то же самое, $p = 1$.

Реализация на псевдокоде чуть-чуть отличается от описанного классического алгоритма.

В классическом алгоритме требуется вычисление дополнительного параметра $m$ для виртуального расширения массива до размера $F_{k+1}$. В данной реализации этот шаг опущен, используется непосредственная работа с исходным массивом размера $n$.

Классический алгоритм использует начальную позицию $F_k - m$, тогда как здесь используется фиксированное начальное смещение $\code{offset} = -1$. Это устраняет необходимость вычисления $m$ и упрощает логику работы с границами массива.

При этом проверки на выход за границы реализованы не через проверку условия $j \le 0$, а через функцию min(offset + fib_m2, n - 1), что еще больше упрощает реализацию.

И, наконец, алгоритм останавливается тогда, когда $\code{fib\_k} \le 1$, а не когда $q = 0 \lor p = 1$. Получается на $1$ итерацию меньше.

В итоге в реализации количество сравнений, совершаемых алгоритмов, на $2$ меньше количества сравнений в классическом варианте. Но считать я буду все равно количество сравнений в классическом алгоритме.

Дерево решений при таком поиске будет представлять собой дерево Фибоначчи. У дерева Фибоначчи порядка $k$ левым поддеревом является дерево Фибоначчи порядка $k-1$, а правым поддеревом является дерево Фибоначчи порядка $k-2$.

При этом высота дерева Фибоначчи равна $k$, где $F_k < n + 1 \le F_{k+1}$. Подставляя формулу Бине можно получить, что высота этого дерева Фибоначчи равна

В бинарном поиске мы делили область поиска пополам. В поиске Фибоначчи мы делили область поиска в соотношении $\vphi$. Давайте рассмотрим общий случай, при котором область поиска делится в соотношении $p : q$. Алгоритм, соответствующий ткому произвольному разделению называется разделённым поиском.

Итак, пусть $p$ и $q$ — положительные числа и $p + q = 1$. Алгоритм разделённого поиска ищет ключ $K$ в отсортированном массиве с $n$ ключами $K_1 < K_2 < \dotsb < K_n$.

Мы сравниваем ключ с номером $np$ с искомым ключом $K$, и в зависимости от результатов сравнения выбираем левую или правую часть массива. Продолжаем эту операцию с получившимся подмассивом.

Пусть $C(n)$ — среднее количество сравнений, необходимых для разделённого поиска в массиве длины $n$. Тогда можно примерно оценить

Возникает такая формула потому, что после сравнения поиск в $n$ элементах сводится с вероятностью $p$ к поиску в примерно $pn$ элементах и с вероятностью $q$ к поиску в примерно $qn$ элементах

Из этой рекурсивной формулы получаем, что

В знаменателе получилась такая интересная формула не случайно.

Давайте делить массив не на $2$ части, а на $m$ частей. Пусть относительные размеры частей будут $p_1, p_2, \dotsc, p_m$, при этом они такие, что $p_1 + p_2 + \dotsb + p_m = 1$.

Нам нужно на каждой итерации определять, какой части области поиска принадлежит искомый элемент. Можно это делать, выполняя $m-1$ сравнение с опорными элементами на границах частей.

Пусть снова $C(n)$ — среднее количество сравнений, необходимых для разделённого поиска в массиве длины $n$. Тогда можно примерно оценить

Формула получилась из тех же самых соображений, что и в случае с $m = 2$: $p_j$ — вероятность попадания в $j$-ю часть массива, в которой находится примерно $p_j n$ элементов.

Слагаемое $m-1$ присутствует в формуле потому, что мы совершаем $m-1$ сравнения для определения части, в которой находится искомый ключ $K$. Если мы работаем в какой-то другой, небинарной логике, это слагаемое следует изменить.

Решая рекуррентное соотношение, получаем

где $\H = - \sum\limits_{j=1}^m p_j \log p_j$ — энтропия распределения $p_1, p_2, \dotsc, p_m$. Основания логарифмов одинаковые.

В этой формуле скрыт глубокий смысл, отсылающий нас к основам теории информации. $\log n$ — полное количество информации, которое нам нужно получить, чтобы найти элемент среди $n$. $\H$ — среднее количество информации, которое мы получаем за один шаг алгоритма, при этом каждый шаг требует $m-1$ сравнений.

Давайте снова возьмем словарь и будем искать в нйм слова. Если нам поступил запрос на поиск слова «абака», то, кажется, нет смысла открывать словарь в середине, ведь слово прям очень близко к началу словаря. Такой подход свойственен нам, людям, и абсолютно чужд для машин. Так научим же их!

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

У нас есть массив упорядоченных ключей $K_1, K_2, K_3, \dotsc, K_{n-1}, K_n$. При этом на ключах нам задано не только линейное отношение порядка, но и способ мерить масштаб. Формально, нам нужно, чтобы ключи были элементами линейного упорядоченного аффинного пространства над линейным упорядоченным полем. Но можно не думать об этих страшных словах и просто считать, что мы ищем среди чисел.

Нам нужно найти в этом массиве номер ключа $K$, то есть такое $j$, что $K_j = K$.

Как и с бинарным поиском, заведем переменные, указывающие на границы области поиска left и right. Но опорный индекс мы будем выбирать не как середину, а будем пытаться предсказывать положение целевого элемента $K$.

Для того, чтобы что-то предположить, нам нужно какое-то основание. Пусть мы будем надеяться на то, что элементы по индексам подчиняются линейной зависимости.

В итоге мы просто линейно интерполируем по двум точкам $\big( \code{left}, a[\code{left}] \big)$ и $\big( \code{right}, a[\code{right}] \big)$, и вычисляем индекс $j$, с надеждой, что $a[j] = K$. Формула вычисления индекса получается

В остальном алгоритм полностью аналогичен бинарному поиску.

Оно $O(\log \log n)$. Надо будет написать доказательство.