The world’s smallest indexing code

index.cs

public class Index<TItem, TKey>
{
    private readonly SortedSet<KeyValuePair<TKey, List<TItem>>> sortedSet;

    public Index(IEnumerable<TItem> items, Func<TItem, TKey> keySelector, Comparer<TKey> keyComparer = null)
    {
        if (keyComparer == null) keyComparer = Comparer<TKey>.Default;
        var keyPairComparer = Comparer<KeyValuePair<TKey, List<TItem>>>.Create((x, y) => keyComparer.Compare(x.Key, y.Key));
        var keyPairs = items.GroupBy(keySelector).Select(x => new KeyValuePair<TKey, List<TItem>>(x.Key, x.ToList()));
        sortedSet = new SortedSet<KeyValuePair<TKey, List<TItem>>>(keyPairs, keyPairComparer);
    }

    public IEnumerable<TItem> All()
    {
        foreach (var keyPair in this.sortedSet)
        {
            foreach (var item in keyPair.Value) yield return item;
        }
    }

    public IEnumerable<TItem> ExactMatchSearch(TKey key)
    {
        return this.RangeSearch(key, key);
    }

    public IEnumerable<TItem> RangeSearch(TKey fromKey, TKey toKey)
    {
        var lowerValue = new KeyValuePair<TKey, List<TItem>>(fromKey, null);
        var upperValue = new KeyValuePair<TKey, List<TItem>>(toKey, null);
        foreach (var keyPair in this.sortedSet.GetViewBetween(lowerValue, upperValue))
        {
            foreach (var item in keyPair.Value) yield return item;
        }
    }
}

program.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp2
{
    static class Program
    {
        static void Main(string[] args)
        {
            var array = new int[] { 8, 5, 1, 11, 2, 2, 3, 1, 5, 5, 1, 2 };
            var index = array.BuildIndex(x => x);
            foreach (var x in index(6, 15))
            {
                Console.WriteLine(x);
            }
        }

        private static int BinarySearchFirstGreaterOrEquals<TItem, TKey>(this TItem[] sortedArray, Func<TItem, TKey> keySelector, TKey key)
        {
            int l = 0; int r = sortedArray.Length - 1;
            if (Comparer<TKey>.Default.Compare(key, keySelector(sortedArray[r])) > 0) return sortedArray.Length;
            while (l < r)
            {
                int m = (l + r) / 2;
                if (Comparer<TKey>.Default.Compare(key, keySelector(sortedArray[m])) > 0)  l = m + 1; 
                else r = m ;
            }
            return l;
        }

        private static IEnumerable<TItem> Search<TItem, TKey>(this TItem[] sortedArray, Func<TItem, TKey> keySelector, TKey from, TKey to)
        {
            for(var index = sortedArray.BinarySearchFirstGreaterOrEquals(keySelector, from); index < sortedArray.Length; index++ )
            {
                var item = sortedArray[index];
                var key = keySelector(item);
                if (Comparer<TKey>.Default.Compare(key, from) < 0) yield break;
                if (Comparer<TKey>.Default.Compare(key, to) > 0) yield break;
                yield return item;
            }
        }

        public static Func<TKey, TKey, IEnumerable<TItem>> BuildIndex<TKey, TItem>(this IEnumerable<TItem> collection, Func<TItem, TKey> keySelector)
        {
            var sortedArray = collection.OrderBy(keySelector).ToArray();
            return (TKey from, TKey to) => sortedArray.Search(keySelector, from, to);
        }
    }
   
}