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

In this post, we will see how to resolve 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++?

Best Answer:

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;

    let res: Result<usize, usize> = 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,
        })
        // Check what we found.
        // Since our comparator never returns `Ordering::Equal`,
        // it would always `Err(idx)`.
        .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();

If you have better answer, please add a comment about this, thank you!

Source: Stackoverflow.com