Метод поиска Фибоначчи — это способ поиска в с использованием алгоритма «разделяй и властвуй», который сужает возможные местоположения с помощью чисел Фибоначчи. Этот метод концептуально похож на двоичный поиск, который многократно делит интервал поиска на две равные половины. Однако поиск Фибоначчи делит массив на две неравные части, размеры которых являются последовательными числами Фибоначчи.

Этот метод имел ключевое преимущество на старом компьютерном оборудовании, где арифметическое деление или операции побитового сдвига были вычислительно дороги по сравнению со сложением и вычитанием. Поскольку последовательность Фибоначчи основана на сложении, этот метод поиска мог быть реализован более эффективно. Хотя на современных процессорах разница в производительности часто незначительна, алгоритм сохраняет теоретический и исторический интерес. В среднем поиск Фибоначчи выполняет примерно на 4% больше сравнений, чем бинарный поиск, и имеет среднюю и худшую сложность (см. «O» большое).

Поиск Фибоначчи также может иметь преимущество при поиске данных, хранящихся в определённых структурах, например, на магнитной ленте, где время поиска сильно зависит от расстояния от текущего положения головки. Он является производным от поиска золотого сечения, алгоритма Джека Кифера (1953) для поиска максимума или минимума унимодальной функции в интервале.

Алгоритм Метод поиск Фибоначчи работает следующим образом: сначала находится наименьшее число Фибоначчи, которое больше или равно длине массива. Пусть это число Фибоначчи будет . Затем алгоритм использует предыдущие числа Фибоначчи и , для проверки массива по индексу, сужая пространство поиска на каждом шаге. Размер шага уменьшается на каждой итерации в соответствии с последовательностью Фибоначчи.

Пусть k определяется как элемент F, массива чисел Фибоначчи. — это размер массива. Если n не является числом Фибоначчи, пусть будет наименьшим числом в F, которое больше n.

Массив чисел Фибоначчи определяется как при , и .

Чтобы проверить, находится ли элемент в списке упорядоченных чисел, выполняются следующие шаги:

Устанавливаем k = m. Если k = 0, останавливаемся. Совпадений нет, элемента в массиве нет. Сравниваем элемент с элементом в . Если элемент совпадает, останавливаемся. Если элемент меньше , отбрасываем элементы от позиции до n. Устанавливаем и возвращаемся к шагу 2. Если элемент больше , отбрасываем элементы от позиции 1 до . Перенумеровываем оставшиеся элементы индексами от 1 до , устанавливаем и возвращаемся к шагу 2.

Альтернативная реализация (из книги "Сортировка и Поиск" Кнута):

Дана таблица записей , ключи которых располагаются в возрастающем порядке. Алгоритм ищет элемент с ключом K. Предположим, что [Инициализация] (в алгоритме p и q будут представлять последовательные числа Фибоначчи) [Сравнение] Если , переходим к Шагу 3; если переходим к Шагу 4; если , алгоритм успешно завершает работу. [Уменьшение i] Если q=0, алгоритм завершается неудачей. В противном случае устанавливаем (что перемещает p и q на одну позицию назад в последовательности Фибоначчи); возвращаемся к Шагу 2 [Увеличение i] Если p=1, алгоритм завершается неудачей. В противном случае устанавливаем (что перемещает p и qна две позиции назад в последовательности Фибоначчи); возвращаемся к Шагу 2

Два варианта алгоритма, представленные выше, всегда делят текущий интервал на больший и меньший подынтервалы. Однако исходный алгоритм, делил бы новый интервал на меньший и больший подынтервалы на шаге 4. Это имеет то преимущество, что новый i ближе к старому i и больше подходит для ускорения поиска на магнитной ленте.

Пример Предположим, мы хотим найти число x = 85 в следующем отсортированном массиве из n = 11 элементов:

[10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]

Находим числа Фибоначчи: Наименьшее число больше или равное n = 11 — это . Таким образом, m = 7. Два предыдущих числа Фибоначчи — и . Мы будем отслеживать смещение (offset) подмассива, в котором ведётся поиск. Первоначально offset = -1. Первое сравнение: Первый индекс сравнения равен i = min(offset + F_6, n-1) = min(-1 + 8, 10) = 7. Мы сравниваем x с элементом по индексу 7: array = 82. Поскольку x = 85 больше, чем 82, мы исключаем элементы с начала до индекса 7. Новое пространство поиска – подмассив, начиная с индекса 8. Мы обновляем числа Фибоначчи, перемещаясь на два шага назад: m = m - 2 = 6 (так что новые числа Фибоначчи будут и ). Обновляем смещение: offset = i = 7. Второе сравнение: Следующий индекс сравнения равен i = min(offset + F_4, n-1) = min(7 + 3, 10) = 10. Сравниваем x с элементом по индексу 10: array = 100. Поскольку x = 85 меньше, чем 100, исключаем элементы от индекса 10 до конца. Обновляем числа Фибоначчи, сдвигаясь на один шаг: m = m - 1 = 5 (новые значения будут и ). Смещение остаётся прежним offset = 7. Третье сравнение: Следующий индекс сравнения равен i = min(offset + F_3, n-1) = min(7 + 2, 10) = 9. Мы сравниваем x с элементом по индексу 9: array = 90. Поскольку x = 85 меньше, чем 90, исключаем элементы, начиная с индекса 9 до конца. Обновляем числа Фибоначчи, сдвигаясь на один шаг: m = m - 1 = 4 (новые значения будут и ). Смещение остаётся прежним offset = 7. Четвёртое сравнение:''' Следующий индекс сравнения равен i = min(offset + F_2, n-1) = min(7 + 1, 10) = 8. Мы сравниваем x с элементом по индексу 8: array = 85. Элемент найден по индексу 8. Алгоритм завершился успешно.

См. также Алгоритм поиска

Примечания

.

Категория:Алгоритмы поиска Категория:Числа Фибоначчи