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

Hm, what did you check so far, maybe [this](http://en.wikipedia.org/wiki/Fibonacci_search_technique)? — home, Sep 29 '11 at 15:16
The fact that you didn't get it only proves that it's too complicated for you, not that the books failed. Learn to accept responsibility! — Blindy, Sep 29 '11 at 15:16
@home I checked that and this as well- http://www.ics.forth.gr/~lourakis/fibsrch/ & a couple of others, including animations. Still unclear. ^_^ — Nilesh, Sep 29 '11 at 15:17
@Blindy I'd be more glad to do it, but unfortunately, I've to do it in my practical file. — Nilesh, Sep 29 '11 at 15:17
Could you point out exactly what you don't understand about it? It's hard for me to guess, especially if you understand binary search. — Anthony Labarre, Sep 29 '11 at 15:18
@Nilesh: Most complex algorithms require you to _study_ them, it's not only about reading a paper. What exactly is not clear to you? — home, Sep 29 '11 at 15:24
@AnthonyLabarre Just updated the question and the things I didn't understand. — Nilesh, Sep 29 '11 at 15:28
p and q are likely upper and lower indexes of the array a[] that you search for the key. — Jens, Sep 29 '11 at 15:32
Perhaps studying http://www.seeingwithc.org/topic4html.html will give you a better understanding. It covers linear search, binary search, and Fibonacci search. It's useful to read the entire article so that by the time you get to the description of Fibonacci search, you're familiar with the author's terminology and coding style. — Jim Mischel, Sep 29 '11 at 15:40

score 10 · Accepted Answer · edited May 23 '17 at 10:29

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.

score 2 · Answer 2 · answered Sep 29 '11 at 16:17

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.

Fibonacci Search

2 Answers2

Linked