Rust二分查找出现attempt to subtract with overflow错误，可变索引异常原因查询

问题原因 #

首先回应你的两个疑问：

• 索引无法正常变更和mut关键字无关，你声明的可变变量本身是可以正常修改的，报错的原因是Rust的无符号整型溢出保护机制触发了panic
• 该问题确实和Rust的类型机制有关：Rust中索引默认使用的usize是无符号整型，不允许出现负值，运行时如果检测到无符号数减法下溢会直接终止程序，也就是你看到的attempt to subtract with overflow报错。

触发报错的具体场景 #

你测试查询0的时候就会触发该问题：

1. 数组最小元素为1，查询0的过程中会不断向左缩小区间，直到start和end都等于0
2. 此时计算得到mid = 0，匹配到val > query的分支，执行end = mid -1
3. usize类型的0减1会得到一个非法的负值，触发溢出panic。

另外你当前的测试用例本身存在错误：assert_eq!(binary_search(&arr, 101).unwrap(), 11);是错误的，101在数组中的索引为10，这个错误也会导致测试不通过。

修复方案 #

方案1：将区间边界类型改为isize #

将start和end改为有符号整型，允许存储负值，避免溢出：

pub fn binary_search(arr: &[i32], query: i32) -> Option<usize> {
    let mut end = arr.len() as isize - 1;
    let mut start = 0isize;

    while start <= end {
        let mid = ((end - start) / 2) + start;
        let mid_index = mid as usize;
        let val = arr[mid_index];

        if val == query {
            return Some(mid_index);
        }

        if val < query {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    None
}

方案2：使用左闭右开区间写法（更推荐） #

改变区间定义逻辑，从初始的[0, len-1]改为[0, len)，循环条件改为start < end，更新右边界时直接赋值为mid，完全避免减法操作：

pub fn binary_search(arr: &[i32], query: i32) -> Option<usize> {
    let mut end = arr.len();
    let mut start = 0;

    while start < end {
        let mid = start + (end - start) / 2;
        match arr[mid].cmp(&query) {
            std::cmp::Ordering::Equal => return Some(mid),
            std::cmp::Ordering::Less => start = mid + 1,
            std::cmp::Ordering::Greater => end = mid,
        }
    }

    None
}

修正后的测试用例 #

#[test]
fn test_binary_search() {
    let arr: [i32; 12] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 101, 1000];
    assert_eq!(binary_search(&arr, 3).unwrap(), 2);
    assert_eq!(binary_search(&arr, 0), None);
    assert_eq!(binary_search(&arr, 101).unwrap(), 10);
    assert_eq!(binary_search(&arr, 1000).unwrap(), 11);
}

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