#### Fast Search

```﻿using System;
using Utilities.Exceptions;

namespace Algorithms.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>
public class FastSearcher
{
/// <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>
public int FindIndex(Span<int> array, int item)
{
if (array.Length == 0)
{
throw new ItemNotFoundException();
}

if (item < array || item > array[^1])
{
throw new ItemNotFoundException();
}

if (array == array[^1])
{
return item == array ? 0 : throw new ItemNotFoundException();
}

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

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

private (int left, int right) ComputeIndices(Span<int> array, int item)
{
var indexBinary = array.Length / 2;

int[] section =
{
array.Length - 1,
item - array,
array[^1] - array,
};
var indexInterpolation = section * section / section;

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

private (int from, int to) SelectSegment(Span<int> array, int left, int right, int item)
{
if (item < array[left])
{
return (0, left - 1);
}

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

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