5
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

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 usizestart and end as usizeend.)

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]);
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.