BinarySearchExtensions.cs

public enum BinarySearchType
{
    /// <summary>
    /// The standard BCL binary search. Returns the index of the first equal item found,
    /// or if there are no equal items, the two's complement of index where it would be inserted.
    /// </summary>
    Fast = 0,
    /// <summary>
    /// Return the index of the first equal item, or if there are no equal items, the index where it would be inserted.
    /// </summary>
    PrependIndex,
    /// <summary>
    /// Return the index following the last equal item, or if there are no equal items, the index where it would be inserted.
    /// </summary>
    AppendIndex
}

public static class BinarySearchExtensions
{
    private interface IInlineComparer<T>
    {
        int Compare(T value);
    }

    private static int BinarySearchInline<T, TCalculator>(this IReadOnlyList<T> sortedList, TCalculator calculator, BinarySearchType searchType)
        where TCalculator : IInlineComparer<T>
    {
        if (calculator == null) throw new ArgumentNullException(nameof(calculator));

        var high = sortedList.Count - 1;
        var low = 0;

        switch (searchType)
        {
            case BinarySearchType.Fast:
                while (low <= high)
                {
                    var mid = (high + low) >> 1;
                    var comparison = calculator.Compare(sortedList[mid]);
                    if (comparison == 0) return mid;
                    if (comparison < 0)
                        low = mid + 1;
                    else
                        high = mid - 1;
                }

                return ~low;

            case BinarySearchType.AppendIndex:
                while (low <= high)
                {
                    var mid = (high + low) >> 1;
                    var comparison = calculator.Compare(sortedList[mid]);
                    if (comparison <= 0)
                        low = mid + 1;
                    else
                        high = mid - 1;
                }

                return low;

            case BinarySearchType.PrependIndex:
                while (low <= high)
                {
                    var mid = (high + low) >> 1;
                    var comparison = calculator.Compare(sortedList[mid]);
                    if (comparison < 0)
                        low = mid + 1;
                    else
                        high = mid - 1;
                }

                return low;

            default:
                throw new InvalidEnumValueException(searchType);
        }
    }

    private struct OtherTypeInlineComparer<T, TComparable> : IInlineComparer<T>
        where T : IComparable<TComparable>
    {
        private readonly TComparable comparableValue;

        public OtherTypeInlineComparer(TComparable comparableValue)
        {
            this.comparableValue = comparableValue;
        }

        public int Compare(T value)
        {
            return value != null ? value.CompareTo(comparableValue) : comparableValue == null ? 0 : -1;
        }
    }

    public static int BinarySearch<T, TComparable>(this IReadOnlyList<T> sortedList, TComparable comparableValue, BinarySearchType searchType = BinarySearchType.Fast)
        where T : IComparable<TComparable>
    {
        return BinarySearchInline(sortedList, new OtherTypeInlineComparer<T, TComparable>(comparableValue), searchType);
    }

    private struct SelectorComparerInlineComparer<T, TOrder> : IInlineComparer<T>
    {
        private readonly Func<T, TOrder> orderSelector;
        private readonly TOrder value;
        private readonly IComparer<TOrder> comparer;

        public SelectorComparerInlineComparer(Func<T, TOrder> orderSelector, TOrder value, IComparer<TOrder> comparer)
        {
            this.orderSelector = orderSelector;
            this.value = value;
            this.comparer = comparer ?? Comparer<TOrder>.Default;
        }

        public int Compare(T value)
        {
            return comparer.Compare(orderSelector.Invoke(value), this.value);
        }
    }

    public static int BinarySearch<T, TOrder>(this IReadOnlyList<T> sortedList, Func<T, TOrder> orderSelector, TOrder value, IComparer<TOrder> comparer = null, BinarySearchType searchType = BinarySearchType.Fast)
    {
        return BinarySearchInline(sortedList, new SelectorComparerInlineComparer<T, TOrder>(orderSelector, value, comparer), searchType);
    }

    private struct ComparerInlineComparer<T> : IInlineComparer<T>
    {
        private readonly T value;
        private readonly IComparer<T> comparer;

        public ComparerInlineComparer(T value, IComparer<T> comparer)
        {
            this.value = value;
            this.comparer = comparer ?? Comparer<T>.Default;
        }

        public int Compare(T value)
        {
            return comparer.Compare(value, this.value);
        }
    }

    public static int BinarySearch<T>(this IReadOnlyList<T> sortedList, T value, IComparer<T> comparer = null, BinarySearchType searchType = BinarySearchType.Fast)
    {
        return BinarySearchInline(sortedList, new ComparerInlineComparer<T>(value, comparer), searchType);
    }
}