**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.

__ADVANTAGES:__

**1.** In the case of random-access memory, this technique can reduce the searching time.

**2.** It only uses only addition and subtraction whereas, binary search requires multiplication or division operations.

**3.** The time complexity is lesser than the complexity of a binary search.

__DISADVANTAGES:__

**1.** Fibonacci search requires 4% more comparisons on average than binary search.

__TIME COMPLEXITY:__

At each step, the list is reduced by 1/3 on average.

So,** the time complexity can be represented** as:

Therefore, in **average case the time complexity of the** **Fibonacci search** is **O(log 3n)**.

Related