Add `lower_bound`, `upper_bound` and `equal_range` for slices where T: Ord to complement `binary_search`

View all comments

Motivation

Fom discussion on https://github.com/rust-lang/rust/pull/45333.

There is demand for lower_bound, upper_bound and equal_range especially for sorted sequences of non-unique elements. In such sequences the aforementioned operations are more interesting and useful than binary_search. The addition of these three ops will complement the support of sorted slices in the standard library.

Proposed APIs

lower_bound

/// Finds the first element in the sorted slice that is _not less_ than `x`.
///
/// Returns the index `a` such that all elements in `self[..a]` are less than `x` and all elements in `self[a..]` are greater or equal to `x`.
///
/// # Examples
/// ```
/// let a = [10, 11, 13, 13, 15];
/// assert_eq!(a.lower_bound(9), 0);
/// assert_eq!(a.lower_bound(10), 0);
/// assert_eq!(a.lower_bound(11), 1);
/// assert_eq!(a.lower_bound(12), 2);
/// assert_eq!(a.lower_bound(13), 2);
/// assert_eq!(a.lower_bound(14), 4);
/// assert_eq!(a.lower_bound(15), 4);
/// assert_eq!(a.lower_bound(16), 5);
/// ```
fn lower_bound(&self, x: &T) -> usize 
where
    T: Ord;

/// `lower_bound` with a comparator.
fn lower_bound_by<'a, F>(&'a self, f: F) -> usize
where
    F: FnMut(&'a T) -> Ordering;

/// `lower_bound` with key extraction.
fn lower_bound_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> usize
where
    B: Ord,
    F: FnMut(&'a T) -> B

upper_bound

/// Finds the first element in the sorted slice that is _greater_ than `x`.
///
/// Returns the index `a` such that all elements in `self[..a]` are less or equal to `x` and all elements in `self[a..]` are greater than `x`.
///
/// # Examples
/// ```
/// let a = [10, 11, 13, 13, 15];
/// assert_eq!(a.upper_bound(9), 0);
/// assert_eq!(a.upper_bound(10), 1);
/// assert_eq!(a.upper_bound(11), 2);
/// assert_eq!(a.upper_bound(12), 2);
/// assert_eq!(a.upper_bound(13), 4);
/// assert_eq!(a.upper_bound(14), 4);
/// assert_eq!(a.upper_bound(15), 5);
/// assert_eq!(a.upper_bound(16), 5);
/// ```
fn upper_bound(&self, x: &T) -> usize
where
    T: Ord;

/// `upper_bound` with a comparator.
fn upper_bound_by<'a, F>(&'a self, f: F) -> usize
where
    F: FnMut(&'a T) -> Ordering;

/// `upper_bound` with key extraction.
fn upper_bound_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> usize
where
    B: Ord,
    F: FnMut(&'a T) -> B

equal_range

/// Finds all elements _equal_ to `x`.
///
/// Returns the `Range` `a..b` such that all elements in `self[..a]` are less than `x`, all elements in `self[a..b]` are equal to `x`, and all elements in `self[b..]` are greater than `x`.
///
/// # Examples
/// ```
/// let a = [10, 11, 13, 13, 15];
///  for i in (9..17) {
///    assert_eq!(a.equal_range(i), (a.lower_bound(i), a.upper_bound(i)));
///  }
/// ```

fn equal_range(&self, x: &T) -> std::ops::Range<usize> 
where
    T: Ord;

/// `equal_range` with a comparator.
fn equal_range_by<'a, F>(&'a self, f: F) -> std::ops::Range<usize> 
where
    F: FnMut(&'a T) -> Ordering;

/// `equal_range` with key extraction.
fn equal_range_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> std::ops::Range<usize> 
where
    B: Ord,
    F: FnMut(&'a T) -> B

Review the discussion linked from Rust PR 45333 and compare the proposed lower_bound, upper_bound, and equal_range APIs, including their comparator and key-extraction variants. The payload names no repository files or tests; completion would require an agreed API design and implementation scope for all three operations.