[API Proposal]: Span<T>.LowerBound, UpperBound binary search

Background and motivation

Custom binary search algorithm implementations are error-prone. Developers must deal with integer overflow, off-by-one bugs, empty arrays, and should decide which variable to return: Left or Right. It is hard to remember (maybe just for me) how to write a proper binary search implementation. I always forget it in within an hour after learning it again.

Built-in .NET implementations like Array.BinarySearch and Span.BinarySearch return the index of the first matching element found. This is sufficient to check if an element is present in a Span, but this approach cannot help, for example, to count elements less than or greater than a given x when the Span contains duplicates of x.

Special API to find boundaries of duplicating elements in Span may help for this cases.

Originally I tried to solve a Leetcode problem, and ended up writing custom binary search. Custom binary search or loop wrapper over Span.BinarySearch is 33% of solution code (20 lines for custom binary search in Span, 40 lines for other logic)

C++ has std::lower_bound/upper_bound and Python has bisect.bisect_left/bisect_right for this purpose.

API Proposal

namespace System;

public class MemoryExtensions
{
  public static int BinarySearch<T>(this Span<T> span, IComparable<T> comparable, BinarySearchKind kind);
  public static int BinarySearch<T, TComparable>(this Span<T> span, TComparable comparable, BinarySearchKind kind) where TComparable : IComparable<T>;
  public static int BinarySearch<T, TComparer>(this Span<T> span, T value, TComparer comparer, BinarySearchKind kind) where TComparer : IComparer<T>;
  public static int BinarySearch<T>(this ReadOnlySpan<T> span, IComparable<T> comparable, BinarySearchKind kind);
  public static int BinarySearch<T, TComparable>(this ReadOnlySpan<T> span, TComparable comparable, BinarySearchKind kind) where TComparable : IComparable<T>;
  public static int BinarySearch<T, TComparer>(this ReadOnlySpan<T> span, T value, TComparer comparer, BinarySearchKind kind) where TComparer : IComparer<T>
}

public enum BinarySearchKind {
  FirstMatchingElement = 0,
  LowerBound = 2,
  UpperBound = 3
}

API Usage

int CountElementsLessThan(Span<int> span, int value)
{
  var lowerBound = span.BinarySearch(value, BinarySearchStrategy.LowerBound);
  return lowerBound < 0 ? ~lowerBound : lowerBound;
}

Alternative design:

int CountElementsLessThan(Span<int> span, int value)
{
  var lowerBound = span.LowerBound(value);
  return lowerBound < 0 ? ~lowerBound : lowerBound;
}

Workaround with existing API:

public int LowerBound(Span<int> span, int value)
{
  int first = span.BinarySearch(value);
  int high = first;
  while (high >= 0)
  {
    first = high;
    high = span[..high].BinarySearch(value);
   }
  return first;
}

public int CountElementsLessThan(Span<int> span, int value)
{
  int lowerBound = LowerBound(span, value);
  return first < 0 ? ~first : first;
}

Alternative Designs

BinarySearchStrategy strategy instead of BinarySearchKind kind

====

Separate methods in MemoryExtensions class for lower/upper bound and range

namespace System;

public class MemoryExtensions
{
  /// <summary>
  /// Searches an entire sorted <see cref="Span{T}"/> for a first element which is not ordered before value
  /// using the specified <see cref="IComparable{T}"/> generic interface.
  /// </summary>
  /// <typeparam name="T">The element type of the span.</typeparam>
  /// <param name="span">The sorted <see cref="Span{T}"/> to search.</param>
  /// <param name="comparable">The <see cref="IComparable{T}"/> to use when comparing.</param>
  /// <returns>
  /// The zero-based index of first <paramref name="comparable"/> occurrence in the sorted <paramref name="span"/>,
  /// if <paramref name="comparable"/> is found; otherwise, a negative number that is the bitwise complement
  /// of the index of the next element that is larger than <paramref name="comparable"/> or, if there is
  /// no larger element, the bitwise complement of <see cref="Span{T}.Length"/>.
  /// </returns>
  /// <exception cref="ArgumentNullException">
  /// <paramref name = "comparable" /> is <see langword="null"/> .
  /// </exception>
  public static int LowerBound<T>(this Span<T> span, IComparable<T> comparable);
  public static int LowerBound<T, TComparable>(this Span<T> span, TComparable comparable) where TComparable : IComparable<T>;
  public static int LowerBound<T, TComparer>(this Span<T> span, T value, TComparer comparer) where TComparer : IComparer<T>;
  public static int LowerBound<T>(this ReadOnlySpan<T> span, IComparable<T> comparable);
  public static int LowerBound<T, TComparable>(this ReadOnlySpan<T> span, TComparable comparable) where TComparable : IComparable<T>;
  public static int LowerBound<T, TComparer>(this ReadOnlySpan<T> span, T value, TComparer comparer) where TComparer : IComparer<T>


  /// <summary>
  /// Searches an entire sorted <see cref="Span{T}"/> for a first element which is ordered after value
  /// using the specified <see cref="IComparable{T}"/> generic interface.
  /// </summary>
  /// <typeparam name="T">The element type of the span.</typeparam>
  /// <param name="span">The sorted <see cref="Span{T}"/> to search.</param>
  /// <param name="comparable">The <see cref="IComparable{T}"/> to use when comparing.</param>
  /// <returns>
  /// The zero-based index of first element which is ordered after <paramref name="comparable"/> in the sorted <paramref name="span"/>,
  /// if <paramref name="comparable"/> is found; otherwise, a negative number that is the bitwise complement
  /// of the index of the next element that is larger than <paramref name="comparable"/> or, if there is
  /// no larger element, the bitwise complement of <see cref="Span{T}.Length"/>.
  /// </returns>
  /// <exception cref="ArgumentNullException">
  /// <paramref name = "comparable" /> is <see langword="null"/> .
  /// </exception>
  public static int UpperBound<T>(this Span<T> span, IComparable<T> comparable);
  public static int UpperBound<T, TComparable>(this Span<T> span, TComparable comparable) where TComparable : IComparable<T>;
  public static int UpperBound<T, TComparer>(this Span<T> span, T value, TComparer comparer) where TComparer : IComparer<T>;
  public static int UpperBound<T>(this ReadOnlySpan<T> span, IComparable<T> comparable);
  public static int UpperBound<T, TComparable>(this ReadOnlySpan<T> span, TComparable comparable) where TComparable : IComparable<T>;
  public static int UpperBound<T, TComparer>(this ReadOnlySpan<T> span, T value, TComparer comparer) where TComparer : IComparer<T>

  // [lowerBound; upperBound), or (upperBound, upperBound) if element is not found
  public static Range BinarySearchRange<T>(this Span<T> span, IComparable<T> comparable);
  public static Range BinarySearchRange<T, TComparable>(this Span<T> span, TComparable comparable) where TComparable : IComparable<T>;
  public static Range BinarySearchRange<T, TComparer>(this Span<T> span, T value, TComparer comparer) where TComparer : IComparer<T>;
  public static Range BinarySearchRange<T>(this ReadOnlySpan<T> span, IComparable<T> comparable);
  public static Range BinarySearchRange<T, TComparable>(this ReadOnlySpan<T> span, TComparable comparable) where TComparable : IComparable<T>;
  public static Range BinarySearchRange<T, TComparer>(this ReadOnlySpan<T> span, T value, TComparer comparer) where TComparer : IComparer<T>
}

Risks

No breaking changes, as existing APIs is not modified

• Should LowerBound/UpperBound return bitwise complement when value is not present for consistency with BinarySearch, or it is better to just return a non-negative index?