News for hackers. Stuff that matters.
Re:Binary Search Reconsidered (2018) by Measter on Tuesday December 29, 2020 @10:11AM (#25570424)
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.

There are no comments on this comment yet.