如果语句与 Rust 中的类型不匹配，则递归函数 [英] Recursive function if statement mismatched types in Rust

问题描述

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);
    }
}

编译器在 if target == list[guess] 上抛出一个错误说

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

我不知道如何重写这个函数以满足类型检查器.我认为这是因为我将返回类型设置为 bool 并且有一个返回函数调用?

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?

推荐答案

dikaiosune 的回答 解释了问题:结果类型你的 if 是 ()，它被返回而不是 bool.

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

然后我只执行一次比较，而不是可能执行两次.如果比较昂贵，可以节省一些时间，但使用 match 看起来也不错:

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

您也可以删除范围的开始和结束部分，并使用 is_empty 作为保护子句.

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

那么如果你搜索一个大于最大值的值，就会出现堆栈溢出的问题......你需要在重复时忽略pivot:

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));
}

如果您不是为了学习目的而实现它，请使用内置的binary_search.

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

这篇关于如果语句与 Rust 中的类型不匹配，则递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！