How to implement binary search in Rust with usize indexes?

Question

I'm trying to understand what is the best way to deal with "overflow" and "underflow" when using usize/u32 variables. For instance, I was trying to implement binary search and came up with a situation where one of the variables may underflow.

Below is my implementation of binary search in Rust. Most implementations I see online avoid the underflow situation by declaring mid to be i32. If I wanted to stick with usize for mid, is my use of checked_sub() necessary?

// 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
}

This part of a leetcode question so I’m unfortunately not allowed to change the function signature.

If I don't use checked_sub() I get an underflow and mid wraps around leading to logic errors with the algorithm. Is a better way to write this?

Answer 1

The language is telling you something useful here, your index variable might underflow and wrapping which would be the default in most other languages isn't really what you want here.

The most idiomatic solution would be to return Option<usize> an index that might not have been found, then you can use the short circuit try operator ? to immediately return None (instead of a sentinel like -1 you'd have to use in other languages) to signal a failure to find the target:

fn binary_search(nums: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    // catches user error of passing an empty slice in
    let mut right = nums.len().checked_sub(1)?;

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

        if nums[mid] == target {
            return Some(mid);
        } else if target > nums[mid] {
            // if we ever overflow we immediately know the item isn't in the
            // slice so we can return None right here and that's what `?` does
            left = mid.checked_add(1)?;
        } else {
            // same as above for underflow
            right = mid.checked_sub(1)?;
        }
    }
    None
}

Note: Switching from taking Vec<i32> to &[i32] still let's you pass in let a: Vec<i32> = … via binary_search(&a, value) but it also accepts arrays and other things that deref to a slice, it also has the added benefit of not consuming the first parameter which really isn't necessary for binary search.

In general, if your variable can over-/underflow use carrying_, checked_, wrapping_,... add,sub, ... as applicable, their use compiles to one or two instructions (i.e. no practical overhead) and they convey what behaviour you want exactly in the event of overflow.

---

If for some reason the method signature is required to be fn(Vec<i32>, i32) -> i32 I recommend you write a wrapper:

fn binary_search(nums: Vec<i32>, target: i32) -> i32 {
    binary_search_implementation(&nums, target).map_or(-1, |x| x as i32)
}

where binary_search_implementation is the plain binary_search from above.

---

Of course in the real world I'd use the provided slice::binary_search:

fn binary_search(nums: Vec<i32>, target: i32) -> i32 {
    nums.binary_search(&target).map_or(-1, |x| x as i32)
}

Answer 2

Rather than using the maximum index of the range where the target could be (i.e. your right variable), if you use one greater than that index then your problem goes away. Your loop condition becomes while left < right, and in the last branch of the conditional, when the target is less than mid, you set right to mid.

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

    while left < right {                     // <= Change from left <= right.
        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;                     // <= Change from using checked_sub,
                                             // Note we're setting right to mid,
                                             // not mid - 1.
        }
    }

    -1
}

This can produce different results from your code in the case when there are duplicates in the vector being searched, in the task you are doing it states the are all unique, so this shouldn’t be a problem.

If you need to keep the upper value being the max index and not one past it, then another simple solution is to use i32 and just cast it whenever you index into the vector. Adding lots of casts this way can often get ungainly though.

fn binary_search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() as i32 - 1;      // <= len() gives usize, so
                                                // we need to cast here.

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

        if nums[mid as usize] == target {       // <= Cast to usize here...
            return mid;
        } else if target > nums[mid as usize] { // <= and here.
            left = mid + 1;
        } else {
            right = mid - 1;                    // <= No worries about 
                                                // underflow here.
        }
    }

    -1
}