FibonacciSearcher.cs

using System;

namespace Algorithms.Search;

/// <summary>
///     Class that implements Fibonacci search algorithm.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public class FibonacciSearcher<T> where T : IComparable<T>
{
    /// <summary>
    ///     Finds the index of the item searched for in the array.
    ///     Time complexity:
    ///     worst-case: O(log n),
    ///     average-case: O(log n),
    ///     best-case: O(1).
    /// </summary>
    /// <param name="array">Sorted array to be searched in. Cannot be null.</param>
    /// <param name="item">Item to be searched for. Cannot be null.</param>
    /// <returns>If an item is found, return index. If the array is empty or an item is not found, return -1.</returns>
    /// <exception cref="ArgumentNullException">Gets thrown when the given array or item is null.</exception>
    public int FindIndex(T[] array, T item)
    {
        if (array is null)
        {
            throw new ArgumentNullException("array");
        }

        if (item is null)
        {
            throw new ArgumentNullException("item");
        }

        var arrayLength = array.Length;

        if (arrayLength > 0)
        {
            // find the smallest Fibonacci number that equals or is greater than the array length
            var fibonacciNumberBeyondPrevious = 0;
            var fibonacciNumPrevious = 1;
            var fibonacciNum = fibonacciNumPrevious;

            while (fibonacciNum <= arrayLength)
            {
                fibonacciNumberBeyondPrevious = fibonacciNumPrevious;
                fibonacciNumPrevious = fibonacciNum;
                fibonacciNum = fibonacciNumberBeyondPrevious + fibonacciNumPrevious;
            }

            // offset to drop the left part of the array
            var offset = -1;

            while (fibonacciNum > 1)
            {
                var index = Math.Min(offset + fibonacciNumberBeyondPrevious, arrayLength - 1);

                switch (item.CompareTo(array[index]))
                {
                    // reject approximately 1/3 of the existing array in front
                    // by moving Fibonacci numbers
                    case > 0:
                        fibonacciNum = fibonacciNumPrevious;
                        fibonacciNumPrevious = fibonacciNumberBeyondPrevious;
                        fibonacciNumberBeyondPrevious = fibonacciNum - fibonacciNumPrevious;
                        offset = index;
                        break;

                    // reject approximately 2/3 of the existing array behind
                    // by moving Fibonacci numbers
                    case < 0:
                        fibonacciNum = fibonacciNumberBeyondPrevious;
                        fibonacciNumPrevious = fibonacciNumPrevious - fibonacciNumberBeyondPrevious;
                        fibonacciNumberBeyondPrevious = fibonacciNum - fibonacciNumPrevious;
                        break;
                    default:
                        return index;
                }
            }

            // check the last element
            if (fibonacciNumPrevious == 1 && item.Equals(array[^1]))
            {
                return arrayLength - 1;
            }
        }

        return -1;
    }
}