Fibonacci Search is another divide and conquer algorithm which is used to find an element in a given list. In this tutorial, we will see how it works, how it is different from binary search, and we will implement it in python.
Pre-requisites
There are two topics we need to understand first before moving onto Fibonacci search.
1. Binary Search
Binary search is a divide and conquers algorithm, meaning that we divide our list in order to find our answer. The given list should be sorted so that we can perform the algorithm.
We look at the middle element of the list, and because the list is sorted, we will know where the target is relative to the middle element. We will either find the target at the middle of the list, or we will eliminate one side from the middle depending on whether the item is smaller or larger than the middle element. After eliminating one side, we repeat this process with the other side.
This way, in every iteration we cut down half of our list, so to find n elements, we will only need log2n iterations.
2. Fibonacci Numbers
Fibonacci numbers are the numbers that form the Fibonacci Series. So let us define the Fibonacci Series first. We can define the series recursively as:
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(0) = 0
We do have a direct way of getting Fibonacci numbers through a formula that involves exponents and the Golden Ratio, but this way is how the series is meant to be perceived.
In the above definition, F(n) means “nth Fibonacci Number”.
So, the 0th Fibonacci number is 0, the 1st Fibonacci number is 1, the 2nd Fibonacci number is the sum of the 1st and 0th Fibonacci numbers, the 3rd Fibonacci number is the sum of the 2nd and 1st Fibonacci numbers, and so on.
Finally, the nth Fibonacci number is the sum of the two Fibonacci numbers before it, i.e. the sum of the (n-1)th and the (n-2)th Fibonacci numbers.
Here is the calculation of the first 10 Fibonacci numbers.
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = 3 + 2 = 5
F(6) = 5 + 3 = 8
F(7) = 8 + 5 = 13
F(8) = 21
F(9) = 34
F(10) = 55
...
So, the Fibonacci series, starting from the 0th is:
F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Implementing Fibonacci Search in Python
Similar to binary search, Fibonacci search is also a divide and conquer algorithm and needs a sorted list. It also divides the list into two parts, checks the target with the item in the centre of the two parts, and eliminates one side based on the comparison. So how exactly is it different from binary search?
In the Fibonacci search, we use the Fibonacci numbers to divide the list into two parts, so it will divide the list into two parts of different lengths. Also, instead of performing division to do that, it performs addition which is less taxing on the CPU. Now let’s dive into the details.
First, we need to have the length of the given list. Then we find the smallest Fibonacci number greater than or equal to the size of the list. That means if the size of the list is 100, then the smallest Fibonacci number greater than 100 is 144. Let us say that this is the nth Fibonacci number. In the above example, 144 is the 12th Fibonacci number.
After this, we move back twice in the Fibonacci series from that number. Essentially, we find the (n-2)th Fibonacci number. So in the above example, we had found the 12th Fibonacci number which is 144, so we need the 10th one which is 55.
We use this as the index to divide the list into two parts. That is, we look at this index in the list, and assuming the list is sorted in increasing order, if the item at this index is smaller than the target, then we eliminate the left side, otherwise, we eliminate the right side. We do this until we find the item we are looking for, which will happen when the calculated index’s item will match the target.
Now let us dive into the code for this algorithm:
def fibonacci_search(lst, target):
size = len(lst)
start = -1
f0 = 0
f1 = 1
f2 = 1
while(f2 < size):
f0 = f1
f1 = f2
f2 = f1 + f0
while(f2 > 1):
index = min(start + f0, size - 1)
if lst[index] < target:
f2 = f1
f1 = f0
f0 = f2 - f1
start = index
elif lst[index] > target:
f2 = f0
f1 = f1 - f0
f0 = f2 - f1
else:
return index
if (f1) and (lst[size - 1] == target):
return size - 1
return None
Now let us try to run it and see it’s output:
Conclusion
In this tutorial, we discussed what Fibonacci numbers are, how they are used in the Fibonacci search algorithm, how the algorithm itself works and we implemented the algorithm in python. Hope you had a great time learning, and see you in the next tutorial.