在Rust中可替代std::lower_bound和std::upper_bound的方法是什么？

C++中的现有工具 #

C++的STL提供了两个实用的二分查找函数：std::lower_bound和std::upper_bound

• std::lower_bound：查找目标值首次出现的位置；若目标值不存在，则返回第一个大于目标值的元素位置。
• std::upper_bound：直接查找第一个大于目标值的元素位置。

将这两个函数结合使用，就能得到包含所有目标值的左闭右开迭代器范围。

Rust中的实现方案 #

Rust切片默认仅提供binary_search方法，它只能返回目标值存在时的任意匹配索引，无法直接实现C++中lower_bound和upper_bound的精准语义。以下是两种实现思路：

基于binary_search的简易实现 #

利用binary_search的返回值推导边界，适合重复元素较少的场景：

实现lower_bound功能

fn lower_bound<T: Ord>(slice: &[T], target: &T) -> usize {
    match slice.binary_search(target) {
        Ok(mut idx) => {
            // 向左遍历找到第一个匹配的位置
            while idx > 0 && slice[idx - 1] == *target {
                idx -= 1;
            }
            idx
        }
        Err(pos) => pos,
    }
}

实现upper_bound功能

fn upper_bound<T: Ord>(slice: &[T], target: &T) -> usize {
    match slice.binary_search(target) {
        Ok(mut idx) => {
            // 向右遍历找到最后一个匹配位置的下一位
            while idx < slice.len() && slice[idx] == *target {
                idx += 1;
            }
            idx
        }
        Err(pos) => pos,
    }
}

高效二分实现（O(log n)时间复杂度） #

直接修改二分逻辑，避免线性遍历，性能和C++ STL函数一致：

高效版lower_bound

fn lower_bound<T: Ord>(slice: &[T], target: &T) -> usize {
    let mut low = 0;
    let mut high = slice.len();
    
    while low < high {
        let mid = low + (high - low) / 2;
        if slice[mid] < *target {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    
    low
}

高效版upper_bound

fn upper_bound<T: Ord>(slice: &[T], target: &T) -> usize {
    let mut low = 0;
    let mut high = slice.len();
    
    while low < high {
        let mid = low + (high - low) / 2;
        if slice[mid] <= *target {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    
    low
}

内容的提问来源于stack exchange，提问作者Angelicos Phosphoros