在 Rust 中使用什么来代替 `std::lower_bound` 和 `std::upper_bound`？

Question

我们在 C++ 中拥有什么

C++ 有两个 STL 函数：

std::lower_bound

和

std::upper_bound

std::lower_bound

找到搜索值的第一个位置（如果存在），或者第一个值更大的位置。

std::upper_bound

找到第一个位置，其值大于请求的值。

这个函数一起允许用户找到半开迭代器范围，其中包含等于搜索值的所有值。

生锈

在 Rust 中，我们只有

binary_search

用于带有一些额外谓词的切片，但它可以返回值等于搜索位置的任何位置。

如何找到第一个值索引或像 C++ 中那样的

last value index + 1

？

Answer 1

您可以使用

std::lower_bound 轻松获得 std::upper_bound

 或 

binary_search_by 的行为。

所以，替换

std::lower_bound

：

    use std::cmp::Ordering;

    let (Ok(lower_bound)|Err(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,
        })
        // 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)
            }
        });

并替换

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();