Binary search in Rust

Question

I am a newbie to rust and wanted to know if this code is following idiomatic rust or can be improved.

use std::cmp::Ordering;


pub fn find(array: &[i32], key: i32) -> Option<usize> {
    if array.is_empty(){
        return None;
    }
    let mut start = 0;
    let mut end = array.len() - 1;
    let mut middle;

    loop {
        middle = (end - start) / 2;
        let middle_element = array[start + middle];
        match key.cmp(&middle_element){
            Ordering::Less => end -= middle,
            Ordering::Greater => start += middle,
            Ordering::Equal => {return Some(start+middle as usize);} ,
        }

        //The slicing syntax produces an unborrowed slice
        //(type: [i32]) which we must then borrow (to give a &[i32]),
        //even if we are slicing a borrowed slice.//More can be read at
        //https://github.com/nrc/r4cppp/blob/master/arrays.md
        if end - start <= 1 {
            break;
        };
    }

    if array[start] == key {
        return Some(start as usize);
    }

    if array[end] == key {
        return Some(end as usize);
    }

    None
}

It has passed all the tests listed on Exercism for binary_search problem.

Answer 1

Style

Spaces and punctuation

if array.is_empty(){

should be

if array.is_empty() {

(likewise match key.cmp(&middle_element){ → match key.cmp(&middle_element) {, etc.)

Ordering::Equal => {return Some(start+middle as usize);} ,

should be

Ordering::Equal => return Some(start + middle as usize),

although really, the comma at the end isn't necessary; you can remove that too.

And there should only be one new line below use std::cmp::Ordering and none above.

Scope

middle isn't used outside the loop, so you can replace:

let mut middle;

loop {
    middle = (end - start) / 2;

with:

loop {
    let middle = (end - start) / 2;

Note how the mut can go away, because the value of middle is only set once (per loop).

Unnecessary cast (as)

Ordering::Equal => {
    return Some(start + middle as usize);
},

The as usize is unnecessary; Rust already knows that you're returning Option<usize>. In fact, both start and middle are already usize, as is start + middle, so Rust isn't even doing anything fancy to get this to work. However, writing as usize makes it seem like those aren't usize, which could end up confusing your reader quite a lot.

(Same with start as usize → start and end as usize → end.)

Misleading comments

This comment:

//The slicing syntax produces an unborrowed slice
//(type: [i32]) which we must then borrow (to give a &[i32]),
//even if we are slicing a borrowed slice.//More can be read at
//https://github.com/nrc/r4cppp/blob/master/arrays.md
if end - start <= 1 {

is misleading, for two reasons:

• It's right above (hence attached to) the wrong piece of code.
• You don't use the slicing syntax (array[4..6]) anywhere in your code; you use the indexing syntax.

Just remove it; perhaps replace it with

let middle_element = array[start + middle];
// cmp requires a reference
match key.cmp(&middle_element) {

or something if you think it would be helpful. Though be aware that let middle_element = array[start + middle] makes a copy of middle_element, so the reference is to middle_element on the stack, not array[start + middle] wherever array is stored.

loop with if and break

if end - start <= 1 {
    break;
};

You're trying to make a do while loop here. However, if end - start <= 1 already, you don't need to enter this loop in the first place. This means you can just use a regular while:

while end - start > 1 {
    let middle = (end - start) / 2;
    let middle_element = array[start + middle];
    // cmp requires a reference
    match key.cmp(&middle_element) {
        Ordering::Less => end -= middle,
        Ordering::Greater => start += middle,
        Ordering::Equal => return Some(start + middle),
    }
}

And now cargo fmt doesn't change the code, and cargo clippy doesn't give any suggestions. Hooray!

Implementation

middle

In my mind, middle should be the index of the middle element – not the difference between start and the middle element. You might want to calculate this as (start + end) / 2 but that risks overflow; fortunately, start + (end - start) / 2 works fine.

So this:

let middle = (end - start) / 2;
let middle_element = array[start + middle];
// cmp requires a reference
match key.cmp(&middle_element) {
    Ordering::Less => end -= middle,
    Ordering::Greater => start += middle,
    Ordering::Equal => return Some(start + middle)
}

becomes:

while end - start > 1 {
    let middle = start + (end - start) / 2;
    let middle_element = array[middle];
    // cmp requires a reference
    match key.cmp(&middle_element) {
        Ordering::Less => end = middle,
        Ordering::Greater => start = middle,
        Ordering::Equal => return Some(middle)
    }
}

Unnecessary variable

Now we've made that change, I think array[middle] is obviously the middle element; so much so that we can remove middle_element entirely and get clearer code:

let middle = start + (end - start) / 2;
// cmp requires a reference
match key.cmp(&array[middle]) {

Ordering ordering

I actually think it'd be clearer if these were in Less, Equal, Greater order:

match key.cmp(&array[middle]) {
    Ordering::Less => end = middle,
    Ordering::Equal => return Some(middle),
    Ordering::Greater => start = middle
}

Implicit return

At the end, it might be clearer to use the implicit return form:

if array[start] == key {
    Some(start)
} else if array[end] == key {
    Some(end)
} else {
    None
}

Addendum: Tests

To make sure I didn't break your code while making these changes, I wrote a test. Tests are good to have (not that this is a particularly good test).

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_find() {
        assert_eq!(find(&[2, 4, 5, 7, 11, 12, 17], 5), Some(2));
        assert_eq!(find(&[], 5), None);
        assert_eq!(find(&[2, 4, 5, 7, 11, 12, 17], 6), None);
        assert_eq!(find(&[-63, -42, 1, 2, 4, 5, 7, 11, 12, 17, 17, 18], 12), Some(8));

        call_find(&[-10, -7, 0, 2, 4, 4, 5, 16, 27, 37, 38, 40, 40, 40, 40, 63, 628, 844, 10000000, 41230456]);
    }

    fn call_find(array: &[i32]) {
        for i in 0..array.len() {
            assert_eq!(array[find(array, array[i]).unwrap()], array[i]);
        }
    }
}