1. Introduction

In this tutorial, let’s study the Fibonacci search algorithm. As the name suggests, Fibonacci search algorithm is a search algorithm that involves the Fibonacci Numbers.

The Fibonacci search method, just like the Binary search method, is a comparison-based searching algorithm that is based on the divide and conquer technique. This search method works on an array that is sorted in the non-decreasing order. Before we dive deep into the internals of this search algorithm, let’s first understand the Fibonacci numbers.

2. Fibonacci Numbers

Fibonacci numbers are a sequence of numbers \{F_n\}_{n=1}^\infty where any term F_{n} is equal to the sum of the previous two terms i.e., F_{n-1} and F_{n-2}. Mathematically, we can define the Fibonacci numbers with the following recurrence equation:

    [F_n = F_{n-1} + F_{n-2}]

With F_1 = F_2 = 1, and conventionally defining F_0 = 0.

With this knowledge, let’s generate a few Fibonacci numbers:

    [F_0 = 1]

    [F_1 = 1]

    [F_2 = F_1+F_0 = 1+1 = 2]

    [F_3 = F_2+F_1 = 2+1 = 3]

    [F_4 = F_3+F_2 = 3+2 = 5]

    [F_5 = F_4+F_3 = 5+3 = 8]

    [...]

Fibonacci numbers play a very important role in the information coding theory that forms the backbone of wireless communication. The Fibonacci numbers are heavily used in various security coding algorithms.

Now that we have developed the general background on the Fibonacci numbers, let’s understand the Fibonacci search algorithm.

Fibonacci search is a comparison-based search technique that uses Dynamic Programming. This uses the Fibonacci numbers to create a search tree and then find the key in this tree.

3.2. Fibonacci Search Algorithm

We carry out the Fibonacci search using the following steps:

  1. To begin, we find a Fibonacci number that is greater than or equal to the size of the given array in which we have to search the key. Formally, we can say that if the size of the array is n then we must find a Fibonacci number F_{k} such that F_{k} \geq n.
  2. The next step is to compute F_{k-1}, F_{k-2}, the offset, and the index value. The index is computed using the offset, n, and F_{k-2}.
  3. Here, we compare the key with the element at index in the array. This comparison will give us one of the following three outcomes:
    1. If the key and array element at index are equal then the key is at position index in the given array. We return it and stop.
    2. If the key is less than the array element at index index, then we search the key in the left sub-tree to F_{k-2}.
    3. If the given key is greater than the array element at index, then we search the right sub-tree to F_{k-2}.
  4. If the key is not found, repeat step 1 to step 5 as long as F_{k-2} \geq 0 i.e., we have a Fibonacci number that is greater than the length of the array n.

So, we can see that after each iteration the size of array n is reduced either by \frac{2}{3} or by \frac{1}{3} of the array.

3.3. Pseudocode of Fibonacci Search Algorithm

In this section, let’s look into the pseudocode of the Fibonacci Search algorithm:

algorithm FibonacciSearchAlgorithm(arr, n, key):
    // INPUT
    //    arr = an array of elements
    //    n = the number of elements in arr
    //    key = the element to search for
    // OUTPUT
    //    index of key in arr or -1

    F_k_2 <- 0
    F_k_1 <- 1
    F_k <- F_k_1 + F_k_2

    // Find the greatest F_k that is less than n
    while F_k <= n:
        F_k_2 <- F_k_1
        F_k_1 <- F_k
        F_k <- F_k_1 + F_k_2

    offset <- -1

    while F_k_2 >= 0:
        index <- min(offset + F_k_2, n - 1)

        if arr[index] < key:
            // we search to left of F_k_2
            F_k <- F_k_1
            F_k_1 <- F_k_2
            F_k_2 <- F_k - F_k_1
            offset <- index

        else if arr[index] > key:
            // we search to right of F_k_2
            F_k <- F_k_2
            F_k_1 <- F_k_1 - F_k_2
            F_k_2 <- F_k - F_k_1

        else:
            // arr[index] == key so we return index
            return index

    // Compare the last element of arr with key
    if F_k_1 and arr[offset + 1] = key:
        return offset + 1

    // key not found in arr
    return -1

Now, we’ll cement our understanding of the Fibonacci search algorithm by going through an example.

Let’s take the following sorted array arr:

    [4, 16, 29, 36, 47, 55, 67, 88, 99, 101, 119, 124]

From here, we invoke the Fibonacci search to find key 101.

Iteration 1: We start with full array so n=12 and offset=-1. So, the smallest Fibonacci number \geq 12 is 13. From this, we find F_{k}=13, F_{k-1}=8, and F_{k-2}=5. Next, we compute index=\min{(offset+F_{k-2}), n-1)}=\min((-1+5), 11)=4. The element at index 4 in arr is 47. Since 101 \geq 47, we move one Fibonacci number down.

Iteration 2: F_{k}=8, F_{k-1}=5, F_{k-2}=3. We compute index=\min{(offset+F_{k-2}), n-1)}=\min((4+3), 11)=7. The element at index 7 in arr is 88. Since 101 \geq 88, we move one Fibonacci number down.

Iteration 3: F_{k}=5, F_{k-1}=3, F_{k-2}=2. We compute index=\min{(offset+F_{k-2}), n-1)}=\min((7+2), 11)=9. The element at index 9 in arr is 101. Since 101 \eq 101, we return index and stop.

We depict these iterations in the following figure:

Fibonacci search example

In this section, we’ll see the space and time complexity of the Fibonacci Search.

The Fibonacci Search scheme shrinks the starting search space by either two-thirds or one-third in every iteration depending upon whether the key is smaller than F_{k-1} or is greater than it. Hence, we can represent it with the following recurrence relation:

    [T(n) = T(\frac{2n}{3}) + T(\frac{n}{3}) + c(1)]

Let’s solve this recurrence relation.

    [T(n) = T(\frac{2n}{3}) + T(\frac{n}{3}) + c(1)]

On average, the search space is reduced by \frac{1}{3}, so we can take \frac{n}{3k} = 1 or n=3k. This also implies k=log(n). Now let’s plug in k for n in this recurrence equation:

    [T(3k) = T(2k) + T(k) + 2c(1)]

    [...]

Finally, we’ll get:

    [T(1) = T(\frac{k}{k}) + 2T(\frac{k}{k}) + T(\frac{k}{k}) + kc(1)]

    [\boldsymbol{T(n)} = \boldsymbol{O(1)} + \boldsymbol{O(1)} + \boldsymbol{log(n)}]

  • Best Case: We can easily say that the best-case time complexity of the the Fibonacci search is \boldsymbol{O(1)}. We’ll find this case when the search key is the first element we start comparing.
  • Worst Case: We can see that the worst case for the Fibonacci search method occurs when the key is always present in the larger subarray. Its worst-case time complexity is \boldsymbol{O(logn)}.
  • Average Case: On average, we shrink the search space by \frac{1}{3}, so the average case time complexity of the Fibonacci search algorithm is \boldsymbol{O(logn)}

Fibonacci search has O(1) space complexity because no extra space other than temporary variables is used.

Although both the Binary search and the Fibonacci search are comparison-based searching methods that use Dynamic Programming, there are many subtle differences between them.

On average, Fibonacci Search uses 4\% more comparisons than Binary search. Binary Search uses division operation (/) to divide range whereas Fibonacci Search doesn’t use / albeit, it uses + and -.

Division and multiplication are costly operations as compared to addition and subtraction. Fibonacci Search reduces the search space by either \frac{2}{3} or \frac{1}{3}. On the other hand, Binary search always shrinks the search space by \frac{1}{2}. Furthermore, the Fibonacci search uses 44\% more lookups in comparison to the Binary search algorithm.

6. Conclusion

In this article, we went through the Fibonacci search algorithm in detail.

We started by explaining Fibonacci numbers and their importance in theoretical computer science. Then, we described the Fibonacci search method by first giving its general idea. Thereafter, we explained all its steps and gave its formal pseudocode. Post that, we showcased its working with an example. We followed this discussion by calculating the space and time complexity of the Fibonacci Search. Then, we compared the Fibonacci search with the Binary search.

We conclude this article by saying that the Fibonacci search is an efficient comparison-based search technique that uses only lightweight operations such as addition and subtraction instead of heavy operations such as bit-shift, multiplication, and division.