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.
Comments and QueriesIf 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.