3 ms·
This is what I ended up with: fn search<T: Ord>(haystack: &[T], needle: &T) -> Result<usize, usize> { let mut range = 0..haystack.len(); wh
by Measter 6y ago
This is what I ended up with:
fn search<T: Ord>(haystack: &[T], needle: &T) -> Result<usize, usize> {
let mut range = 0..haystack.len();
while !range.is_empty() {
if range.len() == 1 {
if &haystack[range.start] == needle {
return Ok(range.start);
} else {
return Err(range.start + 1);
}
}
let search_range = &haystack[range.clone()];
let (left, right) = search_range.split_at(search_range.len() / 2);
if needle < &right[0] {
range.end -= right.len();
} else {
range.start += left.len();
}
}
Err(range.start)
}
I'm not overly happy with the break conditions inside the loop. They feel messy.