4 ms·
Slices in Rust make for a clean solution: fn binary_search<T: Ord>(mut array: &[T], key: T) -> Option<T> { use std::cmp::Ordering::*; while !a
by justinpombrio 6y ago
Slices in Rust make for a clean solution:
fn binary_search<T: Ord>(mut array: &[T], key: T) -> Option<T> {
use std::cmp::Ordering::*;
while !array.is_empty() {
let middle = array.len() / 2;
match key.cmp(&array[middle]) {
Less => array = &array[..middle],
Equal => return Some(key),
Greater => array = &array[middle + 1..],
}
}
None
}
The type &[T] is a slice. Under the hood it consists of a pointer into an array, plus a length. So it (i) does some bookkeeping for you and reduces the number of variables you need by 1, and (ii) avoids the "lower + upper overflow" issue.
- TedShiller 6y agoThat’s considered clean?
- tsimionescu 6y agoWhat do you consider not to be clean? I dislike the fact that it returns a copy of the key, but otherwise it seems quite explicit code that doesn't needlessly get bogged down in error prone integer arithmetic.
- klyrs 6y agoAs I've pointed out in another comment, this implementation loses track of the index. It looks clean enough to my un-rusty eye, but it sacrifices functionality in favor of hiding the arithmetic behind a slice. And __s's comment does it best: use the standard library. And that's a nice implementation (despite the unsafe stuff), which tracks the basepoint and size to keep the arithmetic clean.
- klyrs 6y agoEqual => return Some(key), The article's implementations return the index, not the value being searched for as you've done here. Do slices give access to their underlying offset? Also the article manages a single branch per iteration. How well does this cmp / match perform in comparison?
- __s 6y agoFor reference, this is rust's actual binary search implementation: https://doc.rust-lang.org/src/core/slice/mod.rs.html#1841 https://doc.rust-lang.org/src/core/slice/mod.rs.html#1841 (returns either Ok(index) when element exists, or Err(index) where index is where you'd insert the element when it doesn't exist)
- tsimionescu 6y ago> Do slices give access to their underlying offset? They don't have to, you already have `middle` available, they can just return Some(middle)
- klyrs 6y agoNo, middle is an index into a slice with an arbitrary offset. Unless (with probability ≈ 0.5^log(n)) you've picked the lower half every time before finding the element, that is not the correct index.
- tsimionescu 6y agoOops, you're absolutely right. I completely forgot that the array variable was being modified itself.
- deleted 6y ago[deleted]
- tsimionescu 6y agofn binary_search<T: Ord>(mut array: &[T], key: T) -> Option<T> A more useful signature would have been fn binary_search<T: Ord>(mut array: &[T], key: T) -> Option<usize> And then returning `Some(middle)` on the Equal match. Returning the value you were given or None would be better expressed as returning True/False to avoid the unnecessary copy.
- justinpombrio 6y ago> A more useful signature would have been [returning the index]. Good point! And if you're doing that, there's no reason to use slices. So I guess the only thing to learn from my code... is that slices do useful bookkeeping for problems similar to this, in the case that you don't care about the indices? > Returning the value you were given or None would be better expressed as returning True/False to avoid the unnecessary copy. Just because two values are equal, doesn't mean they're the same. Though my function signature was wonky, regardless.