Fibonacci search
In this article, we will see one more searching algorithm Fibonacci search. This searching algorithm has some similarity with Binary Search that we have seen in our last article. Both of them works on sorted arrays. Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array.
Fibonacci Search Definition (Source : Wikipedia)
In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.
Compared to Binary Search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers. On average, this leads to about 4% more comparisons to be executed.
Binary Search uses division operator to divide range. Fibonacci Search doesn’t use division ( / ), but uses addition (+) and subtraction (-). The benifit we are getting here is on some CPUs division operator is bit costly.
Fibonacci search Algorithm:
Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If n is not a Fibonacci number, let Fm be the smallest number in F that is greater than n.
The array of Fibonacci numbers is defined where Fk+2 = Fk+1 + Fk, when k ≥ 0, F1 = 1, and F0 = 0.
To test whether an item is in the list of ordered numbers, follow these steps:
- Set k = m.
- If k = 0, stop. There is no match; the item is not in the array.
- Compare the item against element in Fk−1.
- If the item matches, stop.
- If the item is less than entry Fk−1, discard the elements from positions Fk−1 + 1 to n. Set k = k − 1 and return to step 2.
- If the item is greater than entry Fk−1, discard the elements from positions 1 to Fk−1. Renumber the remaining elements from 1 to Fk−2, set k = k − 2, and return to step 2.
The time comlexity for the fibonacci search is same as the binary search which is O(log n).
Lets try to incorporate the above algorithm into code. hmm.. lets not do that this time. Try to implement the fibonacci search yourself. If you need any help with that you can always comment in the comment section below. We will be more than happy to help you with the implementation.
These algorithms are for searching elements in array or linear list, however we have also written articles on various Graph Search algorithms like Breadth First Search and Depth First Search.
You will also like to enhance your knowledge by going through our other articles on different algorithms and data structures.
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.
About the Author
Tags: Java, Programming
Comments and Queries
If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:<pre><code class="java"> String foo = "bar"; </code></pre>For more information on supported HTML tags in disqus comment, click here.
