31 lines
629 B
Plaintext
31 lines
629 B
Plaintext
use std::cmp::Ordering::*;
|
|
|
|
//
|
|
// This implementation fails the following test
|
|
//
|
|
#[test]
|
|
fn binary_search_returns_none() {
|
|
let data = vec![1, 2, 3];
|
|
let target = 10;
|
|
assert_eq!(binary_search(&data, &target), None);
|
|
}
|
|
|
|
// Broken, didn't manage to debug sorry.
|
|
fn binary_search<T: Ord>(arr: &[T], elem: &T) -> Option<usize>
|
|
{
|
|
let mut size = arr.len();
|
|
let mut base = 0;
|
|
|
|
while size > 0 {
|
|
size /= 2;
|
|
let mid = base + size;
|
|
base = match arr[mid].cmp(elem) {
|
|
Less => mid,
|
|
Greater => base,
|
|
Equal => return Some(mid)
|
|
};
|
|
}
|
|
|
|
None
|
|
}
|