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 where any term is equal to the sum of the previous two terms i.e., and . Mathematically, we can define the Fibonacci numbers with the following recurrence equation:
With , and conventionally defining .
With this knowledge, let’s generate a few Fibonacci numbers:
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.
3. Fibonacci Search
Now that we have developed the general background on the Fibonacci numbers, let’s understand the Fibonacci search algorithm.
3.1. General Idea Behind Fibonacci Search
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:
- 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 . Formally, we can say that if the size of the array is then we must find a Fibonacci number such that .
- The next step is to compute , , the , and the value. The is computed using the , , and .
- Here, we compare the with the element at in the array. This comparison will give us one of the following three outcomes:
- If the and array element at are equal then the is at position in the given array. We return it and stop.
- If the is less than the array element at index , then we search the key in the left sub-tree to .
- If the given is greater than the array element at , then we search the right sub-tree to .
- If the is not found, repeat step 1 to step 5 as long as i.e., we have a Fibonacci number that is greater than the length of the array .
So, we can see that after each iteration the size of array n is reduced either by or by 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
3.4. An Example of Fibonacci Search
Now, we’ll cement our understanding of the Fibonacci search algorithm by going through an example.
Let’s take the following sorted array :
From here, we invoke the Fibonacci search to find key 101.
Iteration 1: We start with full array so and . So, the smallest Fibonacci number 12 is 13. From this, we find , , and . Next, we compute . The element at in is 47. Since 101 47, we move one Fibonacci number down.
Iteration 2: , , . We compute . The element at in is 88. Since 101 88, we move one Fibonacci number down.
Iteration 3: , , . We compute . The element at in is 101. Since 101 101, we return and stop.
We depict these iterations in the following figure:
4. Space and Time Complexity of Fibonacci Search
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 or is greater than it. Hence, we can represent it with the following recurrence relation:
Let’s solve this recurrence relation.
On average, the search space is reduced by , so we can take or . This also implies . Now let’s plug in for in this recurrence equation:
Finally, we’ll get:
- Best Case: We can easily say that the best-case time complexity of the the Fibonacci search is . 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 .
- Average Case: On average, we shrink the search space by , so the average case time complexity of the Fibonacci search algorithm is
Fibonacci search has space complexity because no extra space other than temporary variables is used.
5. Comparison of Fibonacci Search with Binary Search
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 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 or . On the other hand, Binary search always shrinks the search space by . Furthermore, the Fibonacci search uses 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.