Read-only sorted dictionary based on a lookup table -- https://stackoverflow.com/a/70630789/11178549

SortedLookupDictionary.cs

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

/// <summary>
/// Represents a read-only collection of key/value pairs that are sorted on the key.
/// </summary>
/// <remarks>
/// This structure is based on a lookup table. The keys should be convertible to
/// integer (ordinal) values, and the range of the ordinal values should be small.
/// </remarks>
public class SortedLookupDictionary<TKey, TValue> : IReadOnlyDictionary<TKey, TValue>
{
    private readonly Func<TKey, int> _keyToOrdinal;
    private readonly Func<int, TKey> _ordinalToKey;
    private readonly (int PreviousIndex, int NextIndex, TValue Value)[] _lookup;
    private readonly int _count;
    private readonly int _offset;

    public SortedLookupDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection,
        Func<TKey, int> keyToOrdinal, Func<int, TKey> ordinalToKey)
    {
        _keyToOrdinal = keyToOrdinal;
        _ordinalToKey = ordinalToKey;
        var collection2 = collection
            .Select(e => KeyValuePair.Create(keyToOrdinal(e.Key), e.Value))
            .OrderBy(e => e.Key)
            .ToList();
        _count = collection2.Count;
        if (collection2.Count == 0) { _lookup = new (int, int, TValue)[0]; return; }
        for (int i = 1; i < collection2.Count; i++)
        {
            if (collection2[i].Key == collection2[i - 1].Key)
                throw new ArgumentException("Duplicate key.");
        }
        int minOrdinal = collection2[0].Key;
        int maxOrdinal = collection2[collection2.Count - 1].Key;
        Debug.Assert(minOrdinal <= maxOrdinal);
        _lookup = new (int, int, TValue)[checked(maxOrdinal - minOrdinal + 1)];
        _offset = minOrdinal;
        int previousIndex = -1;
        for (int i1 = 0, i2 = 0; i1 < _lookup.Length; i1++)
        {
            if (i2 < collection2.Count && collection2[i2].Key == i1 + _offset)
            {
                _lookup[i1].Value = collection2[i2].Value;
                i2++; previousIndex = i1;
            }
            _lookup[i1].PreviousIndex = previousIndex;
        }
        int nextIndex = -1;
        for (int i1 = _lookup.Length - 1, i2 = collection2.Count - 1; i1 >= 0; i1--)
        {
            if (i2 >= 0 && collection2[i2].Key == i1 + _offset)
            {
                i2--; nextIndex = i1;
            }
            _lookup[i1].NextIndex = nextIndex;
        }
        Debug.Assert(_lookup.All(e => e.PreviousIndex >= 0 && e.PreviousIndex < _lookup.Length));
        Debug.Assert(_lookup.All(e => e.NextIndex >= 0 && e.NextIndex < _lookup.Length));
        Debug.Assert(_lookup.All(e => e.PreviousIndex <= e.NextIndex));
        Debug.Assert(_lookup.Count(e => e.PreviousIndex == e.NextIndex) == collection2.Count);
        Debug.Assert(_lookup
            .Select((e, i) => (e.PreviousIndex, e.NextIndex, i))
            .Where(e => e.PreviousIndex == e.NextIndex)
            .All(e => e.PreviousIndex == e.i));
        Debug.Assert(_lookup
            .Where(e => e.PreviousIndex != e.NextIndex)
            .All(e => EqualityComparer<TValue>.Default.Equals(e.Value, default)));
        Debug.Assert(_lookup[0].PreviousIndex == 0 && _lookup[0].NextIndex == 0);
        Debug.Assert(_lookup[_lookup.Length - 1].PreviousIndex == _lookup.Length - 1 && _lookup[_lookup.Length - 1].NextIndex == _lookup.Length - 1);
    }

    public int Count => _count;
    public IEnumerable<TKey> Keys => this.Select(p => p.Key);
    public IEnumerable<TValue> Values => this.Select(p => p.Value);
    public TValue this[TKey key] => TryGetValue(key, out var value) ? value : throw new KeyNotFoundException();
    public TKey MinKey => _lookup.Length > 0 ? _ordinalToKey(_offset) : throw new InvalidOperationException();
    public TKey MaxKey => _lookup.Length > 0 ? _ordinalToKey(_lookup.Length - 1 + _offset) : throw new InvalidOperationException();

    public bool ContainsKey(TKey key)
    {
        int index = checked(_keyToOrdinal(key) - _offset);
        if (index < 0 || index >= _lookup.Length) return false;
        return _lookup[index].PreviousIndex == index;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        int index = checked(_keyToOrdinal(key) - _offset);
        if (index < 0 || index >= _lookup.Length) { value = default; return false; }
        value = _lookup[index].Value;
        return _lookup[index].PreviousIndex == index;
    }

    public bool TryGetPrevious(TKey key, out KeyValuePair<TKey, TValue> previous)
    {
        int index = checked(_keyToOrdinal(key) - _offset);
        if (index >= _lookup.Length) index = _lookup.Length;
        if (index - 1 < 0) { previous = default; return false; }
        int previousIndex = _lookup[index - 1].PreviousIndex;
        var previousKey = _ordinalToKey(previousIndex + _offset);
        previous = KeyValuePair.Create(previousKey, _lookup[previousIndex].Value);
        return true;
    }

    public bool TryGetNext(TKey key, out KeyValuePair<TKey, TValue> next)
    {
        int index = checked(_keyToOrdinal(key) - _offset);
        if (index < 0) index = -1;
        if (index + 1 >= _lookup.Length) { next = default; return false; }
        int nextIndex = _lookup[index + 1].NextIndex;
        var nextKey = _ordinalToKey(nextIndex + _offset);
        next = KeyValuePair.Create(nextKey, _lookup[nextIndex].Value);
        return true;
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        for (int i = 0; i < _lookup.Length; i++)
        {
            if (_lookup[i].PreviousIndex == i)
                yield return KeyValuePair.Create(_ordinalToKey(i + _offset), _lookup[i].Value);
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

/*
    // Example
    var entries = new KeyValuePair<char, string>[]
    {
        new('L', "Life"),
        new('G', "Great"),
        new('B', "Ballet"),
        new('F', "Frenzy"),
        new('J', "Jungle"),
    };

    var dictionary = new SortedLookupDictionary<char, string>(entries,
        c => (int)c, i => (char)i);

    Console.WriteLine(String.Join(", ", dictionary.Keys)); // B, F, G, J, L
*/