Fibonacci Search

Somebody please explain me the fibonacci search algorithm.

I have tried numerous resources around and searched a lot, but the algorithm is still unclear. Most of the resources described it in link with binary search, but 开发者_JAVA技巧I didn't understand 'em. I know fibonacci search algorithm is an extension of binary search, which I know quite well.

My books failed to explain as well.

I know about fibonacci numbers defined as F(n) = F(n-1) + F(n-2), so no need to explain that.

Updating the question by adding what exactly I didn't understand as @AnthonyLabarre said:

The book I'm using has strange symbols without any explanations. Posting the algo here, please help.

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);
}

I'll try to keep things short and clear. Let's say you have a sorted Array A. This array has elements in it, in increasing values. You must find a particular element inside this array. You want to partition this whole Array into sub arrays such that the access time to i th element in the Array is not directly proportional to i. That means a non liner quicker method. Here comes Fibonacci Series in help. One of the most important properties of Fibonacci series is the "golden ratio". You partition the array into sub-arrays at indexes which fall in fibonacci series (0,1,1,2,3,5,8,13,21, 34...).

So your array will be partitioned into intervals like 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], and so on. Now since the array is sorted, just by looking at the starting and ending element of any partition will tell you which partition your number lies in. So, you traverse the elements A[0], A[1], A[2], A[3], A[5], A[8], A[13], A[21], A[34]... unless the current element is greater than the element you are looking for. Now you are sure that your number lies between this current element and the last element you visited.

Next, you keep the elements from A[f(i-1)]..A[f(i)], where i is the index you were currently traversing; f(x) is fibonacci series, and repeat the same procedure unless you find your element.

If you try to calculate the complexity of this approach, this comes to be O(log(x)). This has the advantage of reducing the "average" time required to search.

I believe you should be able to write down the code yourself.

The references provided in the comments are correct, but I'll try and word it differently for you.

It continually divides the list into sublists whose length is a number in the Fibonacci sequence (n = F(m)), then it searches at the next to last index which is also in the Fibonacci sequence (F(m-1)).

So if a list or sublist is n items long, where n = F(m), it will search at F(m-1) first, then if the sought value is greater than the found value, it will then work with the sublist from F(m-1)+1 to F(m), or if the sought value is less than the found value, it will work with the sublist from 1 to F(m-1).

Due to the nature of Fibonacci numbers, either of these sublists will also have a length that is a Fibonacci number, and the process will repeat. The advantage of the algorithm is that at each step the next address searched in the list will be closer to the current address than at the same step of a normal binary search, which is why this algorithm has an advantage in slow sequential access media such as tape drives.