CREATE OWN LIBRARY

Fibonacci search is a searching technique that depends on the Fibonacci numbers and it is based on the divide and conquer principle. The Fibonacci numbers are generated as:

F(n + 1) = F(n) + F(n - 1) where F(i) is the ith Fibonacci number. F (0) = 0 and F (1) = 1, these are two initial values of the Fibonacci series.

First few Fibonacci numbers are: 

0, 1, 1, 2, 3, 5, 8, 13, 21, ….

Now for this searching technique, we have to find the smallest Fibonacci number which is greater than or equal to n (the number of elements of the list). Let the two preceding Fibonacci numbers be F(m - 1) and F(m - 2)

First, the searched element will be compared with the range F(m - 2), if the value matches, the position of the element will be printed. If x is lesser than the element then the third Fibonacci variable will be moved two Fibonacci down which will remove the 2/3rd of the unsearched list.

If the searched value is greater than the element, then the third Fibonacci variable will be moved one Fibonacci down which will remove 1/3rd of the unsearched value from the front. 

EXAMPLE:

Suppose the lists of elements are:

Suppose the element is 100 which is to be searched.

The value of n is 7

So, the smallest Fibonacci number which is equal to or greater than 7 is 8. 

F(m) = 8, F(m - 1) = 5 and F(m - 2) = 3

First offset = -1

i = min(offset + 3, n - 1)

  = min (-1 + 3, 6)

   =min (2,6)

   = 2

So, the value of index 2 is 64 will be compared with the searched element (100).

 As 64 is lesser than 100

F(m) = 5, F(m - 1) = 3, F(m - 2) = 2 and the offset = 2

Therefore,

i = min (offset + 3, n - 1)

     = min (2 + 3, 6)

     = min (5, 6)

     = 5 

Again, the value of index 5 is 100 which is the same as searched element 100. As the elements are matched the position of this element will be printed.