如何在Rust中用usize索引实现二分查找并处理溢/下溢？

问题背景 #

在实现Rust版二分查找时，受LeetCode函数签名限制无法修改参数类型，必须使用usize处理数组索引，但遇到了right = mid - 1时的下溢问题（当mid=0时，usize减1会触发值环绕，导致算法逻辑错误）。多数在线实现通过改用i32规避该问题，但如果坚持使用usize，是否必须依赖checked_sub？有没有更简洁的优化写法？

当前实现 #

你当前的代码通过checked_sub和额外的underflow标记处理下溢，但逻辑略显冗余：

// Return -1 if target not found
fn binary_search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;
    let mut underflow = false;

    while left <= right && !underflow {
        let mid = left + (right - left) / 2;

        if nums[mid] == target {
            return mid as i32;
        } else if target > nums[mid] {
            left = mid + 1;
        } else {
            right = mid.checked_sub(1).unwrap_or_else(|| {
                underflow = true;
                0
            });
        }
    }

    -1
}

优化思路与实现 #

不需要依赖checked_sub和额外标记，可通过预判下溢场景直接处理：当mid=0时，进入else分支意味着target < nums[0]，此时数组中不可能存在目标值，直接跳出循环返回-1即可，从根源避免下溢。

优化后的代码：

// Return -1 if target not found
fn binary_search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;

    while left <= right {
        let mid = left + (right - left) / 2;

        match nums[mid].cmp(&target) {
            std::cmp::Ordering::Equal => return mid as i32,
            std::cmp::Ordering::Less => left = mid + 1,
            std::cmp::Ordering::Greater => {
                // mid为0时，目标小于数组最小元素，直接退出
                if mid == 0 {
                    break;
                }
                right = mid - 1;
            }
        }
    }

    -1
}

usize/u32溢出/下溢通用处理方法 #

针对无符号整数的溢出/下溢，可根据场景选择不同策略：

• 溢出预防：比如二分查找中计算mid时，用left + (right - left)/2替代(left + right)/2，避免left + right超过usize最大值导致溢出。
• 下溢处理：
  • 若业务逻辑中可以预判下溢场景（如上述二分查找的mid=0），直接提前终止或返回结果，比使用checked_sub更高效且逻辑清晰。
  • 无法预判时，使用checked_sub（返回Option，需处理None分支）、saturating_sub（下溢时返回0）或wrapping_sub（允许值环绕，仅适用于特定场景）。

内容的提问来源于stack exchange，提问作者Caesar De la Paz III