面试题：Rust向量查找：二分查找的优化实现

Question

假设你有一个已经按升序排序的Rust向量，元素类型为`i32`。请使用二分查找算法查找特定元素。但要求你在常规二分查找基础上进行优化，当向量中存在大量重复元素时，能快速定位到所有重复元素的起始和结束位置。请给出函数定义及代码实现，描述设计思路。

Answer 1

设计思路

1. 常规二分查找用于定位目标元素的一个位置。
2. 找到目标元素后，从该位置向两侧扩展，以确定所有重复元素的起始和结束位置。这样可以避免对整个数组进行遍历，在大量重复元素的情况下提升效率。

代码实现

fn find_all_occurrences(nums: &[i32], target: i32) -> (usize, usize) {
    let mut left = 0;
    let mut right = nums.len() - 1;

    // 常规二分查找
    while left <= right {
        let mid = left + (right - left) / 2;
        if nums[mid] < target {
            left = mid + 1;
        } else if nums[mid] > target {
            right = mid - 1;
        } else {
            // 找到目标元素，向两侧扩展
            let mut start = mid;
            let mut end = mid;
            while start > 0 && nums[start - 1] == target {
                start -= 1;
            }
            while end < nums.len() - 1 && nums[end + 1] == target {
                end += 1;
            }
            return (start, end);
        }
    }
    // 如果未找到，返回 (0, 0)
    return (0, 0);
}

你可以这样调用这个函数：

fn main() {
    let nums = vec![1, 2, 2, 2, 3, 4, 5];
    let target = 2;
    let (start, end) = find_all_occurrences(&nums, target);
    println!("起始位置: {}, 结束位置: {}", start, end);
}

函数定义

fn find_all_occurrences(nums: &[i32], target: i32) -> (usize, usize);

这个函数接受一个i32类型的已排序切片nums和目标元素target，返回目标元素所有重复值的起始和结束位置的索引。如果未找到目标元素，返回(0, 0)。