RecursiveBinarySearcher.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceAlgorithms.Search;

/// <summary>
/// RecursiveBinarySearcher.
/// </summary>
/// <typeparam name="T">Type of searcher target.</typeparam>
publicclassRecursiveBinarySearcher<T>whereT:IComparable<T>
{
/// <summary>
/// Finds index of item in collection that equals to item searched for,
/// time complexity: O(log(n)),
/// space complexity: O(1),
/// where n - collection size.
/// </summary>
/// <param name="collection">Sorted collection to search in.</param>
/// <param name="item">Item to search for.</param>
/// <exception cref="ArgumentNullException">Thrown if input collection is null.</exception>
/// <returns>Index of item that equals to item searched for or -1 if none found.</returns>
publicintFindIndex(IList<T>?collection,Titem)
{
if(collectionisnull)
{
thrownewArgumentNullException(nameof(collection));
}

varleftIndex=0;
varrightIndex=collection.Count-1;

returnFindIndex(collection,item,leftIndex,rightIndex);
}

/// <summary>
/// Finds index of item in array that equals to item searched for,
/// time complexity: O(log(n)),
/// space complexity: O(1),
/// where n - array size.
/// </summary>
/// <param name="collection">Sorted array to search in.</param>
/// <param name="item">Item to search for.</param>
/// <param name="leftIndex">Minimum search range.</param>
/// <param name="rightIndex">Maximum search range.</param>
/// <returns>Index of item that equals to item searched for or -1 if none found.</returns>
privateintFindIndex(IList<T>collection,Titem,intleftIndex,intrightIndex)
{
if(leftIndex>rightIndex)
{
return-1;
}

varmiddleIndex=leftIndex+(rightIndex-leftIndex)/2;
varresult=item.CompareTo(collection[middleIndex]);

returnresultswitch
{
varrwhenr==0=>middleIndex,
varrwhenr>0=>FindIndex(collection,item,middleIndex+1,rightIndex),
varrwhenr<0=>FindIndex(collection,item,leftIndex,middleIndex-1),
 _ =>-1,
};
}
}