BinarySearcher.cs

using System;

namespace Algorithms.Search;

/// <summary>
///     Binary Searcher checks an array for element specified by checking
///     if element is greater or less than the half being checked.
///     time complexity: O(log(n)),
///     space complexity: O(1).
///     Note: Array must be sorted beforehand.
/// </summary>
/// <typeparam name="T">Type of element stored inside array. 2.</typeparam>
public class BinarySearcher<T> where T : IComparable<T>
{
    /// <summary>
    ///     Finds index of an array by using binary search.
    /// </summary>
    /// <param name="sortedData">Sorted array to search in.</param>
    /// <param name="item">Item to search for.</param>
    /// <returns>Index of item that equals to item searched for or -1 if none found.</returns>
    public int FindIndex(T[] sortedData, T item)
    {
        var leftIndex = 0;
        var rightIndex = sortedData.Length - 1;

        while (leftIndex <= rightIndex)
        {
            var middleIndex = leftIndex + (rightIndex - leftIndex) / 2;

            if (item.CompareTo(sortedData[middleIndex]) > 0)
            {
                leftIndex = middleIndex + 1;
                continue;
            }

            if (item.CompareTo(sortedData[middleIndex]) < 0)
            {
                rightIndex = middleIndex - 1;
                continue;
            }

            return middleIndex;
        }

        return -1;
    }
}