Fibonacci Search

Fibonacci Search is a Divide and Conquer algorithm that splits array into two parts in each iteration. Array is divided using Fibonacci Sequence, unlike using middle nodes in case of Binary Search. For each iteration, 2 consecutive numbers in a Fibonacci Sequence is used in decreasing order.

Fibonacci Search has better performance than Linear Search. But compared to Binary Search, this requires about 4% more comparisons on average. The advantage of Fibonacci Search is that it only requires addition and subtraction operations to split the array.

This doesn't make much difference in today's world. But at the time it was introduced in 1953, computing power was very less and division and multiplication operations where much costlier than addition and subtraction.

Time complexity of Fibonacci Search for average and worst cases are represented as O_{(log n)} and Space complexity is O₍₁₎.

Practical use cases of Fibonacci Search are limited as Binary Search perform better in most of the scenarios.
How Fibonacci Search Works

Program starts by finding the first Fibonacci number (we will denote it as f2) that is greater than or equal to the length of the array. For example, if the array size is 10, f2 = 13.

Then previous 2 Fibonacci numbers are stored in 2 variables.
f1 = 8
f0 = 5

Now the array is split into 2 parts of length f0 and f1. In this case, array will be split into two parts of 5 elements each, because even though f1 = 8, there is only 5 elements left after splitting first part with 5 elements (f0 = 5).

Next we can compare the searched item with the final element of part one to identify which block to be discarded.

For next iteration, we need to apply the split on the remaining part of the array using the previous consecutive Fibonacci Sequences.
In above case, for the second iteration;
f2 = 8
f1 = 5
f0 = 3

Repeat this process until searched item is found.

Code Samples

Below are few sample code implementations of Fibonacci Search Algorithm in Python, Java, C# and JavaScript.

import math

#Check algorithm section if any clarification needed in the logic
arry = [10, 12, 15, 19, 22, 25, 28, 30, 35, 40]
find = 35
pos = -1
arrLen = len(arry)

f0, f1, f2 = 0, 1, 1
while (f2 < arrLen):
    f0 = f1
    f1 = f2
    f2 = f0 + f1

start = -1
while (f2 > 1):
    index = min(start + f0, arrLen - 1)
    if (arry[index] < find):
        f2 = f1
        f1 = f0
        f0 = f2 - f1
        start = index
    elif (arry[index] > find):
        f2 = f0
        f1 = f1 - f0
        f0 = f2 - f1
    else:
        pos = index
        break

if (f1 == 1 and arry[arrLen - 1] == find):
    pos = arrLen - 1

if(pos > -1):
    print("Element found at position : ", pos)
else:
    print("Element not found")

class FibonacciSearch   
{
    public static void main(String[] args)   
    {  
        //Check algorithm section if any clarification needed in the logic
        int[] arry = { 10, 12, 15, 19, 22, 25, 28, 30, 35, 40 };
        int find = 35;
        int pos = -1;
        int arrLen = arry.length;

        int f0 = 0;
        int f1 = 1;
        int f2 = 1;
        while (f2 < arrLen)
        {
            f0 = f1;
            f1 = f2;
            f2 = f0 + f1;
        }

        int start = -1;
        while (f2 > 1)
        {
            int index = Math.min(start + f0, arrLen - 1);
            if (arry[index] < find)
            {
                f2 = f1;
                f1 = f0;
                f0 = f2 - f1;
                start = index;
            }
            else if (arry[index] > find)
            {
                f2 = f0;
                f1 = f1 - f0;
                f0 = f2 - f1;
            }
            else
            {
                pos = index;
                break;
            }
        }

        if (f1 == 1 && arry[arrLen - 1] == find)
            pos = arrLen - 1;

        if (pos > -1)
            System.out.println("Element found at position : " + pos);
        else
            System.out.println("Element not found");
    }
}

using System;
using System.Threading;

namespace DSA
{
   class Program
   {
       public static void Main()
       {
           //Check algorithm section if any clarification needed in the logic
           int[] arry = { 10, 12, 15, 19, 22, 25, 28, 30, 35, 40 };
           int find = 35;
           int pos = -1;
           int arrLen = arry.Length;

           int f0 = 0;
           int f1 = 1;
           int f2 = 1;
           while (f2 < arrLen)
           {
               f0 = f1;
               f1 = f2;
               f2 = f0 + f1;
           }

           int start = -1;
           while (f2 > 1)
           {
               int index = Math.Min(start + f0, arrLen - 1);
               if (arry[index] < find)
               {
                   f2 = f1;
                   f1 = f0;
                   f0 = f2 - f1;
                   start = index;
               }
               else if (arry[index] > find)
               {
                   f2 = f0;
                   f1 = f1 - f0;
                   f0 = f2 - f1;
               }
               else
               {
                   pos = index;
                   break;
               }
           }

           if (f1 == 1 && arry[arrLen - 1] == find)
               pos = arrLen - 1;

           if (pos > -1)
               Console.Write("Element found at position : " + pos);
           else
               Console.Write("Element not found");

           Thread.Sleep(5000);
       }
   }
}

function fibonacciSearch(find) {
    var arry = [ 10, 12, 15, 19, 22, 25, 28, 30, 35, 40 ];
    var pos = -1;
    var arrLen = arry.length;

    var f0 = 0;
    var f1 = 1;
    var f2 = 1;
    while (f2 < arrLen) {
        f0 = f1;
        f1 = f2;
        f2 = f0 + f1;
    }

    var start = -1;
    while (f2 > 1)
    {
        var index = Math.min(start + f0, arrLen - 1);
        if (arry[index] < find)
        {
            f2 = f1;
            f1 = f0;
            f0 = f2 - f1;
            start = index;
        }
        else if (arry[index] > find)
        {
            f2 = f0;
            f1 = f1 - f0;
            f0 = f2 - f1;
        }
        else
        {
            pos = index;
            break;
        }
    }

    if (f1 == 1 && arry[arrLen - 1] == find)
        pos = arrLen - 1;

    if (pos > -1)
        alert("Element found at position : " + pos);
    else
        alert("Element not found");
    return false;
}

var find = 35;
fibonacciSearch(find);

Fibonacci Search

How Fibonacci Search Works

Code Samples