What to use instead of `std::lower_bound` and `std::upper_bound` in Rust?

Question

What we have in C++

C++ has two STL functions: std::lower_bound and std::upper_bound

std::lower_bound finds first position of searched value if it exists, or position of first value greater.

std::upper_bound finds first position with greater value than requested.

Together this functions allows user to find half open iterator range which contains all values equal to searched one.

In Rust

In Rust we have only binary_search for slices with some extra predicates but it can return any positions where value equal to searched one.

How I can find first value index or last value index + 1 like in C++?

Answer 1

You can easily get behaviour of std::lower_bound or std::upper_bound in Rust using binary_search_by.

So, replacement of std::lower_bound:

use std::cmp::Ordering;

// This have exact same behaviour as C++ std::lower_bound.
let lower_bound = my_sorted_slice
    .binary_search_by(|element| match element.cmp(&searched_value) {
        // Since we try to find position of first element,
        // we treat all equal values as greater to move left.
        Ordering::Equal => Ordering::Greater,
        ord => ord,
    })
    // Since our comparator never returns `Ordering::Equal`,
    // it would always `Err(idx)`.
    .unwrap_err();

// Another version if we want to have Ok or Err
// like Rust std binary_search.
let (Ok(lower_bound) | Err(lower_bound)) = my_sorted_slice
    .binary_search_by(|element| match element.cmp(&searched_value) {
        Ordering::Equal => Ordering::Greater,
        ord => ord,
    })
    // Check what we found.
    .or_else(|idx| {
        if my_sorted_slice.get(idx) == Some(&searched_value) {
            Ok(idx)
        } else {
            Err(idx)
        }
    });

And replacement of std::upper_bound:

use std::cmp::Ordering;

let res: usize = my_sorted_slice
    .binary_search_by(|element| match element.cmp(&searched_value) {
        // Since we try to find position right after searched value,
        // we treat all equal values as less to move right.
        Ordering::Equal => Ordering::Less,
        ord => ord,
    })
    // Since `std::upper_bound` always return position
    // which doesn't point to searched value,
    // we would always get `Err` value from bsearch.
    .unwrap_err();