Примеры: Вход

Поиск Фибоначчи
Дан отсортированный массив arr [ ] размера n и элемент x, который нужно найти в нем. Возвращает индекс x, если он присутствует в массиве, иначе возвращает -1.
Примеры:
Вход: arr [ ] = {2, 3, 4, 10, 40}, x = 10
Вывод: 3
Элемент x присутствует в индексе 3.
Вход: arr [ ] = {2, 3, 4, 10, 40}, x = 11
Вывод: -1
Элемент x отсутствует.
Поиск Фибоначчи — это метод, основанный на сравнении, который использует числа Фибоначчи для поиска элемента в отсортированном массиве.
Сходства с Бинарный Поиск : 

1. 
   Работает для отсортированный массивы
   
2. 
   Алгоритм «разделяй и властвуй».
   
3. 
   Имеет временную сложность Log n.
   

Отличия с Бинарный Поиск :

1. 
   Поиск Фибоначчи делит заданный массив на неравные части
   
2. 
   Двоичный поиск использует оператор деления для разделения диапазона. Поиск Фибоначчи не использует /, но использует + и -. разделение оператор Может быть дорого на некоторый процессоры .
   
3. 
   Поиск Фибоначчи исследует относительно более близкие элементы на последующих этапах. Поэтому, когда входной массив велик и не помещается в кэш ЦП или даже в ОЗУ, поиск Фибоначчи может быть полезен.
   

Фон: 
Числа Фибоначчи рекурсивно определяются как F( n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1. Первые несколько чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Наблюдения: 
Ниже наблюдение используется для устранения диапазона и, следовательно, для сложности O (log (n)).
F( n - 2) и прибл . (1/3)*F(n) и
F( n - 1) и прибл . (2/3)*F(n).
Алгоритм: 
Пусть искомый элемент равен x.
Идея состоит в том, чтобы сначала найти наименьшее число Фибоначчи, которое больше или равно длине данного массива. Пусть найденное число Фибоначчи равно fib ( m-е число Фибоначчи). Мы используем (m-2) -е число Фибоначчи в качестве индекса (если это допустимый индекс). Пусть (m-2)'- ое число Фибоначчи равно i , мы сравниваем arr [ i ] с x, если x совпадает, мы возвращаем i . В противном случае, если x больше, мы повторяемся для подмассива после i , иначе мы повторяемся для подмассива до i .
Ниже приведен полный алгоритм.
Пусть arr [0..n-1] будет входным массивом, а искомый элемент будет x.

1. 
   Найдите наименьшее число Фибоначчи, большее или равное n. Пусть это число будет fibM [m-е число Фибоначчи]. Пусть два числа Фибоначчи, предшествующие ему, будут fibMm1 [(m-1)-е число Фибоначчи] и fibMm2 [(m-2)-е число Фибоначчи].
   
2. 
   Пока в массиве есть элементы для проверки:
   
   1. 
      Сравните x с последним элементом диапазона, покрываемого fibMm2.
      
   2. 
      Если x совпадает , вернуть индекс
      
   3. 
      Иначе Если x меньше элемента, переместите три переменные Фибоначчи на два числа Фибоначчи вниз, что указывает на удаление приблизительно двух третей оставшегося массива.
      
   4. 
      В противном случае x больше элемента, переместите три переменные Фибоначчи на один Фибоначчи вниз. Сбросить смещение на индекс. Вместе они указывают на удаление приблизительно одной трети оставшегося массива.
      
3. 
   Поскольку для сравнения может остаться один элемент, проверьте, равен ли fibMm1 1. Если да, сравните x с этим оставшимся элементом. Если совпадение, вернуть index.
   

Рекомендуется: сначала попробуйте свой подход на {IDE} , прежде чем переходить к решению.