Поиск Фибоначчи

Question

Кто-нибудь, пожалуйста, объясните мне алгоритм поиска Фибоначчи.

Я перепробовал множество ресурсов и много искал, но алгоритм все еще неясен. Большинство ресурсов описали это в связи с бинарным поиском, но я не понял их. Я знаю, что алгоритм поиска Фибоначчи - это расширение бинарного поиска, которое я знаю довольно хорошо.

Мои книги также не смогли объяснить.

Я знаю о числах Фибоначчи, определенных как F (n) = F (n-1) + F (n-2), поэтому объяснять это не нужно.

Обновление вопроса, добавив, что именно я не понял, так как @AnthonyLabarre сказал:

Книга, которую я использую, имеет странные символы без каких-либо объяснений. Размещая алгоритм здесь, пожалуйста, помогите.

if(key == a[mid]) return mid; // understood this, comes from binary search
if(key > a[mid]) {
  if(p == 1) return -1; // What is p? It comes as a function arg
  mid = mid + q; //Now what's this q? Again comes a function arg
  p = p - q; // Commented as p=fib(k-4)
  q = q-p; // q = fib(k-5)
 } else // key < a[mid] {
  if(q == 0) return -1;
  mid = mid - q;
  temp = p - q;
  p = q; // p=fib(k-3)
  q = temp; // q = fib(k-4)
  return fibsearch(a, key, mid, p, q);
}

Answer 1

Я постараюсь, чтобы все было коротко и ясно.Допустим, у вас есть отсортированный массив A .Этот массив содержит элементы в возрастающих значениях.Вы должны найти определенный элемент внутри этого массива.Вы хотите разбить весь этот массив на подмассивы так, чтобы время доступа к i -ому элементу в массиве не было прямо пропорционально i .Это означает, что не лайнер более быстрый метод.В помощь приходит Серия Фибоначчи .Одним из наиболее важных свойств ряда Фибоначчи является « золотое сечение ».Вы разбиваете массив на подмассивы по индексам, которые входят в ряд Фибоначчи (0,1,1,2,3,5,8,13,21, 34 ...).

Таким образом, ваш массив будет разбит на интервалы, такие как A [ 0 ] ... A [ 1 ], A [ 1 ]...A [ 1 ], A [ 1 ] ... A [ 2 ], A [ 2 ] ...A [ 3 ], A [ 3 ] ... A [ 5 ], A [ 5 ] ... A [ 13 ], A [ 13 ] ... A [ 21 ], A [ 21 ] ... A [ 34 ] и так далее.Теперь, когда массив отсортирован, просто глядя на начальный и конечный элемент любого раздела, вы узнаете, в каком разделе находится ваш номер. Итак, вы пересекаете элементы A [ 0 ], A [ 1 ], A [ 2 ], A [ 3 ], A [ 5 ], A [ 8 ], A [ 13 ], A [ 21 ], A [ 34 ] ... если текущий элемент больше, чем искомый элемент.Теперь вы уверены, что ваш номер лежит между этим текущим элементом и последним элементом, который вы посетили.

Далее, вы сохраняете элементы от A [ f (i-1) ] .. A[ f (i) ], где i - индекс, который вы в настоящее время просматривали;f ( x ) - ряд Фибоначчи, и повторите ту же процедуру, если не найдете свой элемент.

Если вы попытаетесь вычислить сложность этого подхода, этобыть O (log (x)).Преимущество этого заключается в уменьшении «среднего» времени, необходимого для поиска.

Полагаю, вы сможете написать код самостоятельно.

Answer 2

Ссылки, приведенные в комментариях, верны, но я постараюсь сформулировать это по-другому для вас.

Он непрерывно делит список на подсписки, длина которых является числом в последовательности Фибоначчи (n = F(m)), затем он ищет следующий за последним индекс, который также находится в последовательности Фибоначчи (F (m-1)).

Так, если список или подсписок имеет длину n элементов, где n = F (m), он сначала будет искать в F (m-1), а затем, если искомое значение больше найденного значения, онозатем будет работать с подсписком от F (m-1) +1 до F (m), или, если искомое значение меньше найденного значения, он будет работать с подсписком от 1 до F (m-1).

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