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]
说
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,并且有一个返回函数调用?
dikaiosune的答案解释了问题:您的结果类型为if
is ()
,而不是返回的类型bool
。
这是一些习惯性地编写代码的几种方法:
我先用隐式返回值编写它:
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
:
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
用于guard子句。
然后,如果您搜索的值大于最大值,则会出现堆栈溢出的问题……在重复执行时,您需要忽略数据透视表:
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
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句