JumpSearcher.cs

using System;

namespace Algorithms.Search;

/// <summary>
///     Jump Search checks fewer elements by jumping ahead by fixed steps.
///     The optimal steps to jump is √n, where n refers to the number of elements in the array.
///     Time Complexity: O(√n)
///     Note: The array has to be sorted beforehand.
/// </summary>
/// <typeparam name="T">Type of the array element.</typeparam>
public class JumpSearcher<T> where T : IComparable<T>
{
    /// <summary>
    ///     Find the index of the item searched for in the array.
    /// </summary>
    /// <param name="sortedArray">Sorted array to be search in. Cannot be null.</param>
    /// <param name="searchItem">Item to be search for. Cannot be null.</param>
    /// <returns>If item is found, return index. If array is empty or item not found, return -1.</returns>
    public int FindIndex(T[] sortedArray, T searchItem)
    {
        if (sortedArray is null)
        {
            throw new ArgumentNullException("sortedArray");
        }

        if (searchItem is null)
        {
            throw new ArgumentNullException("searchItem");
        }

        int jumpStep = (int)Math.Floor(Math.Sqrt(sortedArray.Length));
        int currentIndex = 0;
        int nextIndex = jumpStep;

        if (sortedArray.Length != 0)
        {
            while (sortedArray[nextIndex - 1].CompareTo(searchItem) < 0)
            {
                currentIndex = nextIndex;
                nextIndex += jumpStep;

                if (nextIndex >= sortedArray.Length)
                {
                    nextIndex = sortedArray.Length - 1;
                    break;
                }
            }

            for (int i = currentIndex; i <= nextIndex; i++)
            {
                if (sortedArray[i].CompareTo(searchItem) == 0)
                {
                    return i;
                }
            }
        }

        return -1;
    }
}