В информатике метод поиска Фибоначчи - это метод поиска в отсортированном массиве с использованием деления и алгоритм захвата, который сужает возможные местоположения с помощью чисел Фибоначчи. По сравнению с бинарным поиском, где отсортированный массив делится на две части равного размера, одна из которых исследуется далее, поиск Фибоначчи делит массив на две части, размеры которых являются последовательными числами Фибоначчи. В среднем это приводит к увеличению числа выполняемых сравнений примерно на 4%, но имеет то преимущество, что для вычисления индексов элементов массива, к которым осуществляется доступ, требуется только сложение и вычитание, в то время как классический двоичный поиск требует сдвига битов, деления или умножения, операции, которые были менее распространены во время первой публикации поиска Фибоначчи. Поиск Фибоначчи имеет среднюю и худшую сложность O (log n) (см. нотация Big O ).
Последовательность Фибоначчи обладает тем свойством, что число является суммой двух своих предшественников. Следовательно, последовательность может быть вычислена путем повторного сложения. Отношение двух последовательных чисел приближается к золотому сечению, 1,618... Двоичный поиск работает путем деления области поиска на равные части (1: 1). Поиск по Фибоначчи может разделить его на части, приближающиеся к 1: 1,618, при использовании более простых операций.
Если элементы, в которых выполняется поиск, имеют неоднородное хранилище памяти доступа (т. Е. Время, необходимое для доступа к местоположению хранилища, зависит от местоположения, к которому осуществляется доступ), поиск Фибоначчи может иметь преимущество перед двоичным поиском в небольшом сокращении среднее время, необходимое для доступа к месту хранения. Если машина, выполняющая поиск, имеет прямое отображение кэш ЦП, двоичный поиск может привести к большему количеству промахов в кэше, потому что элементы, к которым осуществляется доступ, часто имеют тенденцию собираться только в нескольких строках кэша; это смягчается путем разделения массива на части, которые не имеют степени двойки. Если данные хранятся на магнитной ленте , где время поиска зависит от текущего положения головки, компромисс между более длительным временем поиска и большим количеством сравнений может привести к алгоритму поиска, который искажен аналогично поиску Фибоначчи.
Поиск по Фибоначчи происходит от поиска по золотому сечению, алгоритма Джека Кифера (1953) для поиска максимума или минимума унимодальной функции в интервале.
Пусть k определяется как элемент в F, массиве чисел Фибоначчи. n = F m - размер массива. Если n не является числом Фибоначчи, пусть F m будет наименьшим числом в F, которое больше n.
Массив чисел Фибоначчи определяется где F k + 2 = F k + 1 + F k, когда k ≥ 0, F 1 = 1 и F 0 = 0.
Чтобы проверить, находится ли элемент в списке упорядоченных номеров, выполните следующие действия:
Альтернативная реализация (из «Сортировка и поиск» Кнута):
Для данной таблицы записей R 1, R 2,..., R N, ключи которых расположены в порядке возрастания K 1< K2<... < KN, алгоритм ищет заданный аргумент K. Предположим, N + 1 = F k + 1
Шаг 1. [Инициализация] i ← F k, p ← F k -1, q ← F k-2 (на протяжении всего алгоритма p и q будут последовательными числами Фибоначчи)
Шаг 2. [Сравнить] Если K < Ki, переходите к шагу 3; если K>K i перейти к этапу 4; и если K = K i, алгоритм успешно завершается.
Шаг 3. [Уменьшение i] Если q = 0, алгоритм завершается неудачно. В противном случае установите (i, p, q) ← (i - q, q, p - q) (который перемещает p и q на одну позицию назад в последовательности Фибоначчи); затем вернитесь к шагу 2
шагу 4. [Увеличить i] Если p = 1, алгоритм завершится безуспешно. В противном случае установите (i, p, q) ← (i + q, p - q, 2q - p) (который перемещает p и q на две позиции назад в последовательности Фибоначчи); и вернуться к шагу 2
Два варианта алгоритма, представленные выше, всегда делят текущий интервал на больший и меньший подынтервалы. Исходный алгоритм, однако, разделил бы новый интервал на меньший и больший подынтервалы на шаге 4. Это имеет то преимущество, что новый i ближе к старому i и больше подходит для ускорения поиска на магнитной ленте.