Fast Searcher Algorithm

The Fast Searcher Algorithm is an advanced data search technique designed to efficiently search and retrieve relevant information from large datasets. This algorithm employs sophisticated data structures, indexing, and search strategies to provide rapid access to the desired information, making it an ideal solution for applications that require quick query responses, such as search engines, databases, and recommendation systems. The primary goal of the Fast Searcher Algorithm is to minimize the time spent searching through the data by narrowing down the search space, reducing computational complexity, and optimizing search operations. Underlying the Fast Searcher Algorithm are various mechanisms, such as tree-based structures, hashing techniques, and pre-processing methods, that contribute to its high-speed performance. These mechanisms work in tandem to organize and index the data in a way that allows for faster and more efficient search operations. For instance, tree-based structures like binary search trees, trie trees, and k-d trees break down the data into hierarchical structures that facilitate quicker searches. Similarly, hashing techniques map data to specific memory locations, allowing for constant-time access and retrieval. Additionally, pre-processing methods, such as caching, data compression, and data partitioning, further enhance search performance by reducing the amount of data to be searched and minimizing the number of disk accesses required. By leveraging these techniques, the Fast Searcher Algorithm delivers fast and accurate search results, making it a valuable tool in the rapidly evolving world of big data and information retrieval.
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(int[] array, int item) => FindIndex(array, item, 0);

        private int FindIndex(int[] array, int item, int offset)
        {
            if (item < array[0] || item > array[array.Length - 1])
            {
                throw new ItemNotFoundException();
            }

            if (array[0] == array[array.Length - 1])
            {
                return item == array[0] ? offset : throw new ItemNotFoundException();
            }

            var indexBinary = array.Length / 2;

            int[] section =
            {
                array.Length - 1,
                item - array[0],
                array[array.Length - 1] - array[0],
            };

            var indexInterpolation = section[0] * section[1] / section[2];

            var (i1, i2) = indexBinary > indexInterpolation
                ? (indexInterpolation, indexBinary)
                : (indexBinary, indexInterpolation);

            int from, to;
            if (item == array[i1])
            {
                return offset + i1;
            }

            if (item == array[i2])
            {
                return offset + i2;
            }

            if (item < array[i1])
            {
                @from = 0;
                to = i1 - 1;
            }
            else if (item < array[i2])
            {
                @from = i1 + 1;
                to = i2 - 1;
            }
            else
            {
                @from = i2 + 1;
                to = array.Length - 1;
            }

            if (from >= to)
            {
                throw new ItemNotFoundException();
            }

            var segment = new int[to - from + 1];
            Array.Copy(array, from, segment, 0, segment.Length);
            return FindIndex(segment, item, offset + from);
        }
    }
}

LANGUAGE:

DARK MODE: