InterpolationSearch.cs

namespace Algorithms.Search;

/// <summary>
///     Class that implements interpolation search algorithm.
/// </summary>
public static class InterpolationSearch
{
    /// <summary>
    ///     Finds the index of the item searched for in the array.
    ///     Algorithm performance:
    ///     worst-case: O(n),
    ///     average-case: O(log(log(n))),
    ///     best-case: O(1).
    /// </summary>
    /// <param name="sortedArray">Array with sorted elements to be searched in. Cannot be null.</param>
    /// <param name="val">Value to be searched for. Cannot be null.</param>
    /// <returns>If an item is found, return index, else return -1.</returns>
    public static int FindIndex(int[] sortedArray, int val)
    {
        var start = 0;
        var end = sortedArray.Length - 1;

        while (start <= end && val >= sortedArray[start] && val <= sortedArray[end])
        {
            var denominator = (sortedArray[end] - sortedArray[start]) * (val - sortedArray[start]);

            if (denominator == 0)
            {
                denominator = 1;
            }

            var pos = start + (end - start) / denominator;

            if (sortedArray[pos] == val)
            {
                return pos;
            }

            if (sortedArray[pos] < val)
            {
                start = pos + 1;
            }
            else
            {
                end = pos - 1;
            }
        }

        return -1;
    }
}