Fibonacci Search

Another interesting search algorithm is Fibonacci search. It exploits the Fibonacci sequence to find an item in an ordered list. This algorithm iteratively divides the input array into subsections, similar to binary search. However, unlike the latter, the array is divided into unequal parts, making it more efficient for large data sets.

Fibonacci sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It starts with 0 and 1, and from there each subsequent number is the sum of the two preceding ones. So, the sequence starts like 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

How it works

The Fibonacci search algorithm starts by generating the smallest Fibonacci number that is greater than or equal to the size of the array being searched. This Fibonacci number, F, becomes the starting point for the search.

The algorithm then compares the element being searched for with the element in the array at the position of the (F-2)th Fibonacci number. If the element being searched for is larger, the algorithm excludes the first F-2 elements and repeats the process on the remaining array. If the element being searched for is smaller, it excludes the last F-1 elements and repeats the process on the remaining array.

This process repeats, with the algorithm continuing to "remove" portions of the array until the searched-for element is found, or until the array has been fully explored.

public static class SearchAlgorithms
{
    public static int FibonacciSearch(int[] arr, int x)
    {
        var fibMMm2 = 0; // (m-2)'th Fibonacci No.
        var fibMMm1 = 1; // (m-1)'th Fibonacci No.
        var fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
        var n = arr.Length;

        while (fibM < n)
        {
            fibMMm2 = fibMMm1;
            fibMMm1 = fibM;
            fibM = fibMMm2 + fibMMm1;
        }

        var offset = -1;

        while (fibM > 1)
        {
            var i = Math.Min(offset + fibMMm2, n - 1);

            if (arr[i] < x)
            {
                fibM = fibMMm1;
                fibMMm1 = fibMMm2;
                fibMMm2 = fibM - fibMMm1;
                offset = i;
            }
            else if (arr[i] > x)
            {
                fibM = fibMMm2;
                fibMMm1 -= fibMMm2;
                fibMMm2 = fibM - fibMMm1;
            }
            else
            {
                return i;
            }
        }

        return fibMMm1 == 1 && arr[offset + 1] == x ? offset + 1 : -1;
    }
}

Time complexity

The time complexity is O(log n) because, with each comparison, the algorithm reduces the size of the search space by about a factor of 2.

Space complexity

The space complexity is O(1), which means it uses constant space. Since it does not require additional space, it is ideal for situations where memory space is limited.

Conclusion

Fibonacci search is an impactful and efficient search algorithm known for its exceptional performance, especially with large datasets. This algorithm requires no additional space, which positions it as a perfect fit for situations where memory space might be constrained. Its unique capability to work well with dynamically changing datasets, not requiring access to the entire dataset simultaneously, further highlights its robustness. However, it's worth noting that for a successful Fibonacci search, the array needs to be sorted first, which implies an investment of time and resources. Also, it may not be ideal for small arrays and is generally more complex to comprehend and implement when compared to other search algorithms such as linear search and binary search.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)