3 ms·
The modifications that this article makes to the original version [1,2] are not a good idea. The modified version in this article cannot properly be used to sea
by jules 2y ago
The modifications that this article makes to the original version [1,2] are not a good idea. The modified version in this article cannot properly be used to search an array, for example (due to the extra "sanity checks", which would cause out-of-bounds errors). The API is also made more complex, returning a pair of options of indices rather than a pair of indices. You really just want the pair of indices!
If you do sanity checks in Rust then you should panic instead of returning options. However, in this case you cannot do the sanity checks, because the contract of the function is that it will only call the predicate strictly between l and r (i.e., only on indices returned by mid). Further, given the initial sanity checks, the sanity checks inside the loop body are redundant, as the loop invariant ensures that those checks never fail.
[1] https://julesjacobs.com/notes/binarysearch/binarysearch.pdf https://julesjacobs.com/notes/binarysearch/binarysearch.pdf
[2] https://byorgey.wordpress.com/2023/01/01/competitive-programming-in-haskell-better-binary-search/ https://byorgey.wordpress.com/2023/01/01/competitive-program...
Here is a Rust implementation of the original:
pub fn search<T: Mid, G>(predicate: G, mut l: T, mut r: T) -> (T, T)
where G: Fn(&T) -> bool
{
loop {
match l.mid(&r) {
None => return (l, r),
Some(m) => {
if predicate(&m) { r = m }
else { l = m }
}
}
}
}
Or, traitless:
pub fn search<T, H, G>(mid: H, predicate: G, mut l: T, mut r: T) -> (T, T)
where H: Fn(&T,&T) -> Option<T>, G: Fn(&T) -> bool
{
loop {
match mid(&l, &r) {
None => return (l, r),
Some(m) => {
if predicate(&m) { r = m }
else { l = m }
}
}
}
}