再帰関数錆

Question

中の文の不一致種類

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

場合、コンパイラは、私は型チェッカーを満たすために、この機能を書き換える方法を見つけ出すことはできません

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 

を言っif target == list[guess]にエラーがスローされます。戻り値の型がboolに設定されており、戻り値の関数呼び出しがあるので、それは仮定していますか？

Answer 1

dikaiosune's answerは、問題を説明します：

EDITは：明示的なリターンO/W後世のために、ここでは同じコードだあなたifの結果の型ではなく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) 
    } 
} 

その後、私は一度だけの比較を実行したい、代わりに潜在的に2回

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を使用することができます。比較は高価ですが、それはまたmatchで素敵に見える場合は少し時間を節約することができます。あなたが最大の値よりも大きな値を検索する場合次に、スタックオーバーフローの問題があります

...あなたは定期的な時にピボットを無視する必要があります：あなたはが実装されていない場合

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を使用してください。

Answer 2

ここでの問題は、それがelse句を欠いて、任意の値に評価されていない文がタイプ()を持っているので、錆がとして戻り値をif/else if/else ifブロックを評価していることです。ちなみに、あなたが提示したコードは網羅的にすべての可能性をカバーしています（スライスの現在のインデックスの項目はターゲットよりも等しいか、より小さいか、または大きいです）。しかし、コンパイラは、最後にelse句：

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：この機能は、変更可能な参照を必要としないので、私は上記の私のコードのように定期的な参照を使用してお勧めします。

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