FastSearcher.cs

usingSystem;
usingUtilities.Exceptions;

namespaceAlgorithms.Search;

/// <summary>
/// The idea: you could combine the advantages from both binary-search and interpolation search algorithm.
/// Time complexity:
/// worst case: Item couldn't be found: O(log n),
/// average case: O(log log n),
/// best case: O(1).
/// Note: This algorithm is recursive and the array has to be sorted beforehand.
/// </summary>
publicclassFastSearcher
{
/// <summary>
/// Finds index of first item in array that satisfies specified term
/// throws ItemNotFoundException if the item couldn't be found.
/// </summary>
/// <param name="array">Span of sorted numbers which will be used to find the item.</param>
/// <param name="item">Term to check against.</param>
/// <returns>Index of first item that satisfies term.</returns>
/// <exception cref="ItemNotFoundException"> Gets thrown when the given item couldn't be found in the array.</exception>
publicintFindIndex(Span<int>array,intitem)
{
if(array.Length==0)
{
thrownewItemNotFoundException();
}

if(item<array[0]||item>array[^1])
{
thrownewItemNotFoundException();
}

if(array[0]==array[^1])
{
returnitem==array[0]?0:thrownewItemNotFoundException();
}

var(left,right)=ComputeIndices(array,item);
var(from,to)=SelectSegment(array,left,right,item);

returnfrom+FindIndex(array.Slice(from,to-from+1),item);
}

private(intLeft,intRight)ComputeIndices(Span<int>array,intitem)
{
varindexBinary=array.Length/2;

int[]section=
{
array.Length-1,
item-array[0],
array[^1]-array[0],
};
varindexInterpolation=section[0]*section[1]/section[2];

// Left is min and right is max of the indices
returnindexInterpolation>indexBinary
?(indexBinary,indexInterpolation)
:(indexInterpolation,indexBinary);
}

private(intFrom,intTo)SelectSegment(Span<int>array,intleft,intright,intitem)
{
if(item<array[left])
{
return(0,left-1);
}

if(item<array[right])
{
return(left,right-1);
}

return(right,array.Length-1);
}
}