Fibonacci Search

Question

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

Answer 1

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.