Существует два алгоритма, называемых «поиск Фибоначчи».
Статья, которую вы связали , посвящена численному алгоритму для нахождения максимума или минимума определенных функций. Это оптимальный алгоритм для этой задачи. Эта проблема достаточно отличается от проблемы бинарного поиска, поэтому она должна быть очевидна для любого конкретного случая, который уместен.
Другой вид поиска Фибоначчи действительно атакует ту же проблему, что и бинарный поиск. Бинарный поиск по сути всегда лучше. Кнут пишет, что поиск по Фибоначчи «предпочтителен на некоторых компьютерах, поскольку он включает только сложение и вычитание, а не деление на 2». Но почти все компьютеры используют двоичную арифметику, в которой деление на 2 проще , чем сложение и вычитание.
(В статье в Википедии в настоящее время утверждается, что поиск по Фибоначчи может иметь лучшую локализацию ссылок, утверждение Кнут делает , а не . Это может , возможно, но это вводит в заблуждение. Тесты вводят в заблуждение. выполненные поиском по Фибоначчи ближе друг к другу именно в той степени, в которой они менее полезны для сужения диапазона, в среднем это приведет к большему количеству чтений из большего числа частей таблицы, а не к меньшему. Если записи на самом деле хранятся на ленте, так что время поиска доминирует, тогда поиск по Фибоначчи может превзойти бинарный поиск - но в этом случае оба алгоритма далеки от оптимальных.)