Recursive function if statement mismatched types i

问题:

fn recursive_binary_search<T: Ord>(list: &mut [T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }
    let guess = list.len() / 2;
    if target == list[guess] {
        return true;
    } else if list[guess] > target {
        return recursive_binary_search(&mut list[0..guess], target);
    } else if list[guess] < target {
        return recursive_binary_search(&mut list[guess..list.len()], target);
    }
}

the compiler throws an error on if target == list[guess] saying

src/main.rs:33:5: 39:6 error: mismatched types [E0308]
src/main.rs:33     if target == list[guess] {
                   ^
src/main.rs:33:5: 39:6 help: run `rustc --explain E0308` to see a detailed explanation
src/main.rs:33:5: 39:6 note: expected type `bool`
src/main.rs:33:5: 39:6 note:    found type `()`
error: aborting due to previous error

I can't figure out how to rewrite this function to satisfy the type checker. I assume it is because I have the return type set to bool and there is a return function call?

回答1:

dikaiosune's answer explains the problem: the resulting type of your if is (), which is being returned instead of a bool.

Here's a few ways of writing the code a bit more idiomatically:

I'd start by writing it with implicit returns:

fn recursive_binary_search<T: Ord + Eq>(list: &[T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }

    let guess = list.len() / 2;

    if target == list[guess] {
        true
    } else if list[guess] > target {
        recursive_binary_search(&list[0..guess], target)
    } else {
        recursive_binary_search(&list[guess..list.len()], target)
    }
}

Then I'd perform the compare just once, instead of potentially twice. Could save a bit of time if comparisons are expensive, but it also looks nice with the match:

use std::cmp::Ordering;

fn recursive_binary_search<T: Ord + Eq>(list: &[T], target: T) -> bool {
    if list.is_empty() {
        return false;
    }

    let guess = list.len() / 2;

    match target.cmp(&list[guess]) {
        Ordering::Less    => recursive_binary_search(&list[..guess], target),
        Ordering::Greater => recursive_binary_search(&list[guess..], target),
        Ordering::Equal   => true,
    }
}

You can also drop the beginning and end parts of the ranges, and use is_empty for the guard clause.

Then there's the problem of the stack overflow if you search for a value larger than the biggest value... you need to ignore the pivot when recurring:

use std::cmp::Ordering;

fn recursive_binary_search<T: Ord>(list: &[T], target: T) -> bool {
    if list.is_empty() {
        return false;
    }

    let guess = list.len() / 2;

    match target.cmp(&list[guess]) {
        Ordering::Less    => recursive_binary_search(&list[..guess], target),
        Ordering::Greater => recursive_binary_search(&list[guess+1..], target),
        Ordering::Equal   => true,
    }
}

fn main() {
    assert!(!recursive_binary_search(&[1,2,3,4,5], 0));
    assert!(recursive_binary_search(&[1,2,3,4,5], 1));
    assert!(recursive_binary_search(&[1,2,3,4,5], 2));
    assert!(recursive_binary_search(&[1,2,3,4,5], 3));
    assert!(recursive_binary_search(&[1,2,3,4,5], 4));
    assert!(recursive_binary_search(&[1,2,3,4,5], 5));
    assert!(!recursive_binary_search(&[1,2,3,4,5], 6));
}

If you aren't implementing this for learning purposes, use the built-in binary_search.

回答2:

The issue here is that Rust evaluates the if/else if/else if block as the return value because it lacks an else clause, and statements which don't evaluate to any value have the type (). Incidentally, the code you've presented does exhaustively cover all possibilities (the item at the current index of the slice is either equal to, less than, or greater than the target), but the compiler doesn't know that unless you give it an else clause at the end:

fn recursive_binary_search<T: Ord + Eq>(list: &[T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }
    let guess = list.len() / 2;
    if target == list[guess] {
        return true;
    } else if list[guess] > target {
        return recursive_binary_search(&list[0..guess], target);
    } else {
        return recursive_binary_search(&list[guess..list.len()], target);
    }
}

PS: This function doesn't require mutable references, so I'd recommend using regular references as in my code above.

EDIT: For posterity, here's the same code w/o explicit returns:

fn recursive_binary_search<T: Ord>(list: &[T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }
    let guess = list.len() / 2;
    if target == list[guess] {
        true
    } else if list[guess] > target {
        recursive_binary_search(&list[0..guess], target)
    } else {
        recursive_binary_search(&list[guess..list.len()], target)
    }
}