### 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` ```rust /// 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` ```rust /// 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` ```rust /// 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 ```