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 = F_{m} is the array size. If n is not a Fibonacci number, let F_{m} be the smallest number in F that is greater than n.
The array of Fibonacci numbers is defined where F_{k+2} = F_{k+1} + F_{k}, when k ≥ 0, F_{1} = 1, and F_{0} = 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 F_{k−1}.
- If the item matches, stop.
- If the item is less than entry F_{k−1}, discard the elements from positions F_{k−1} + 1 to n. Set k = k − 1 and return to step 2.
- If the item is greater than entry F_{k−1}, discard the elements from positions 1 to F_{k−1}. Renumber the remaining elements from 1 to F_{k−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.
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.