9 ms·

my-new-rust-binary-search

59 points by ChadNauseam 2y ago

gnuvince 2y ago
> Just look at the code. How could it be simpler? Cannot tell if this is a joke.
- Aeolos 2y ago
  Which part do you find complicated? The code itself looks very straightforward, two preconditions and a loop. I don't see any significant difference in terms of complexity compared to any other low-level systems programming language. It's obviously a bit more verbose than python or haskell, but those are not targeting the same audience.
- IshKebab 2y ago
  It looks extremely simple to me. I definitely have never seen a simpler binary search implementation (though in fairness it punts the midpoint calculation). Why do you think it's a joke?
- johnisgood 2y ago
  Yeah, Perl is simple, too, then.
IncreasePosts 2y ago
> This one also makes that assumption, but in some cases if that assumption is violated it returns an error rather than silently returning a meaningless Sometimes returning an error and sometimes returning an incorrect value doesn't sound like a binary search that is "absolutely reliable". Also, s/consolation/consultation/
- edflsafoiewq 2y ago
  It doesn't seem possible to determine if the predicate is monotonic without doing a full scan, thus not being a binary search.
- fallingsquirrel 2y ago
  It seems to me that it's impossible for a binary search to detect all errors. The precondition is that the list must be sorted, and to fully verify that assumption would be O(n). That would make your binary search no better than a linear search. So I can forgive the best-effort error checking.
  - ratmice 2y ago
    In theory at least that precondition could be guaranteed by a newtype like SortedList without requiring any linear scan, that would work at least for most cases where lists are sorted by an algorithm. Though not necessarily custom data which is constructed sorted/maintains it's sorting outside the algorithm, but you could perhaps have an unsafe constructor for your SortedList type. That should avoid a linear scan...
  - _proofs 2y ago
    i am not sure i see a use case where that precondition is anything but mandatory (and at least a requirement in app space for the related data), if youre intending on making practical use of the algo. if theres a risk that your input is unstable in ordering, then reaching for bsearch seems like a "premature optimization", and youd be better off with a straightforward linear scan until requirements (or your kanguage of choice's bst/heap/rbt equivalent), or data is preprocessed upstream in a way that makes sense for the contexts wanting to use it.
- Almondsetat 2y ago
  Binary search only works if you suppose the data is well structured. If you perform the search and in the meantime you spot a passing inconsistency, you can interrupt everything and throw an error. But other than that, checking the entire structure negates the entire point of the algorithm
- deleted 2y ago
  [deleted]
deleted 2y ago
[deleted]
eknkc 2y ago
While the implementation is straightforward enough, this post clearly shows me why I don’t like Rust. So, the function accepts two values that implement Mid trait. And there is a blanket implementation for Mid that applies to anything can be added, substracted, divided etc and can be derived from a u8. So now this will make every numeric type a Mid. (Which, as the author states only an example I guess) I can read and understand how this works here. But when I’m in a larger code base, I can not find what trait implementation made what possible. With all the trait bounds and implicit conversions happening around and macros implementing traits on stuff it becomes a shit stew in a hurry. And everyone always reaches to the most clever way to do things. I mean, does Mid need to be a trait? I guess it works beautifully yeah. I’d prefer to pass a midpoint calculator function instead. I guess this turned into a rant. I actually really like Rust the language but I think I don’t like Rust codebases basically. It is the least readable language I’ve seen not because of the syntax but because of all the cleverness going on around the traits and macros.
- worik 2y ago
  > I actually really like Rust the language but I think I don’t like Rust codebases basically. And > everyone always reaches to the most clever way to do things. Yes oh yes Rust was a brilliant idea spoilt by too much cleverness I'm hoping for Rust II. A smaller language, with a bigger standard library and no dependence on run times. By "no dependence on run times." I mean no async/await. It is an abomination in Rust
  - Conscat 2y ago
    There already exist many affine-typed languages with fewer features than Rust. When you phrase it like "Rust but with weaker type safety and higher-overhead abstractions" one might see why this premise fails to gain much traction, though.
  - aw1621107 2y ago
    > By "no dependence on run times." I mean no async/await. It is an abomination in Rust Out of curiosity, what alternative would you have preferred to see, if any?
rurban 2y ago
You can omit the runtime sorted checks via proper types. Only accept sorted arrays or lists, and enforce them with such a class. This would make it convenient, faster and safer. It would also take the sort check from the object, and not as extra argument.
- im3w1l 2y ago
  In theory I like this, but it raises the question of how it would work in practice; in practice people create non-sorted lists and then sort them in-place. Maybe you could have the sort method return a sorted-token that certifies that a given array is sorted. And the token would read-only borrow the array, to ensure no one can modify the array as long as the token is valid. Is it even possible for a rust function to take a mutable borrow as a parameter, decay it to an immutable borrow and store that somewhere, such that other people can borrow the parameter after the function has returned?
  - aw1621107 2y ago
    > Is it even possible for a rust function to take a mutable borrow as a parameter, decay it to an immutable borrow and store that somewhere, such that other people can borrow the parameter after the function has returned? I think it's possible under some scenarios with the appropriate lifetimes? For example, https://rust.godbolt.org/z/6fe8c4sf4 https://rust.godbolt.org/z/6fe8c4sf4: struct Magic<'a> { reference: &'a i32 } impl<'a> Magic<'a> { fn new<'b: 'a>(source: &'b mut i32) -> Magic<'a> { Magic { reference: source } } } fn double(i: &i32) -> i32 { i * 2 } fn main() { let mut i = 0; let m = Magic::new(&mut i); double(m.reference); } I think this will stop working once the compiler can no longer see that the lifetimes work out, but I think that makes sense - there's a mutable object underlying the mutable borrow, and the compiler needs to verify that no one else can get another mutable borrow while the derived immutable borrows are live.
    - im3w1l 2y ago
      So let's for completenes circle back to the usecase of a certified sorted array, it would be something like this struct Sorted<'a> { reference: &'a [i32] } impl<'a> Sorted<'a> { fn in_place<'b: 'a>(source: &'b mut [i32]) -> Sorted<'a> { source.sort(); Sorted { reference: source } } } fn use_sorted_array(sorted_arr: &Sorted) { let arr = sorted_arr.reference; println!("{} {} {}", arr[0], arr[1], arr[2]); } fn main() { let mut arr = [2, 3, 1]; let sorted_arr = Sorted::in_place(&mut arr); use_sorted_array(&sorted_arr); } You might also want to add methods on Sorted for creating a Option<Sorted> by verifying the sortedness of an immutable reference and a method that copies an array and sorts it (it would need to return a struct of a Box for managing the lifetime and a Sorted pointing into the box, or something I guess, probably need to use Pin?) --- On a completely separate note, this will actually not work for the binary search in the article in question, as it uses binary search on a predicate. Having a sorted array doesn't guarantee that the predicate will be monotonic.
re 2y ago
> You want one that doesn't require a consolation with a manual to remember if it returns the first value that's greater or the last value that's lower. ... No more needing to remember "does this return the highest index whose value is lower than the value I'm searching for, or the lowest index whose value is greater than the value I'm searching for?". This one returns both, so you can use whichever you need for your use case. This (italicized part) feels like a weird requirement. Function/API documentation (which this author's code lacks) is important, and I don't think I ever write a call to an unfamiliar function without checking the docs for it. Assuming that you know what a function does based on the name alone is a recipe for buggy code. This is also a kind of unusual formulation of binary search which searches across a monotonic function space rather than a sequence. I get that this is more general and can be used to implement the latter, but a less general interface that only works on sequences is IMO more intuitive: in that case, I expect it to return either the index of the target number, or the index where it should be inserted if not found. It's somewhat telling that the author doesn't offer any code examples demonstrating how to use this wonderful general function to solve the common use case of finding an element in a sorted vector, or inserting a new one into the correct location.
- edflsafoiewq 2y ago
  The interface is nicer for keyframe interpolation eg. the problem where you have a list of (X,Y) pairs and you want to find the two pairs that straddle a given x and interpolate between them. In that case, search(|&i| v[i].0 >= x, 0, v.len() - 1) handles the three cases "before the beginning", "after the end", and "between two pairs" fairly naturally.
leni536 2y ago
> The only case where it returns (None, None) are those when it detects non-monotonicity in your predicate (returning false when a lower input returned true). So if you know your predicate is monotonic, feel free to hit this case with a panic!("should never happen"). Empty range?
- edflsafoiewq 2y ago
  No such thing, the range is inclusive of the l and r endpoints.
orlp 2y ago
This binary search is pretty bad in my opinion. Some issues: 1. It doesn't support the empty array, because l and r are both inclusive. 2. It performs way more predicate tests than necessary. 3. An incorrectly implemented Mid trait causes a silent infinite loop. 4. If a fundamental programming error in the sanity check is detected it just silently returns Nones instead of panicking.
- ramon156 2y ago
  3 is not a good reason. i It's the developer's job to not screw up. What's the alternative?
  - orlp 2y ago
    I would normally agree, but the author went out of their way to check for error conditions in their binary search. I think a silent infinite loop is antithetical to that.
  - gpm 2y ago
    This is a case where less abstraction would make the bug a lot more obvious. Binary search is simple enough that I don't think a generic implementation of it is worth introducing the possibilities of errors at a distance like that one.
  - deleted 2y ago
    [deleted]
- bqmjjx0kac 2y ago
  5) The provided Mid implementation will panic for signed integer types. There's a part where it sorts `self` and `other`, then subtracts. let difference = *large - *small; Suppose large is 0 and small is i32::MIN. Kaboom, right? For reference: https://github.com/dfinity/ic/commit/79aca8ede9fccd322e0e01183ee72c0bc3ed2e61#diff-41cafdf6b2a805c65ef8163a866c3924a49b2487d6588dda414cfd42005cc44cR19 https://github.com/dfinity/ic/commit/79aca8ede9fccd322e0e011...
- dvt 2y ago
  Agree with basically everything here, plus I would add that this method also has weird ergonomics. For example there is technically a midpoint between these two: `0b10u64.mid(&-20)`--but you get a weird compiler error ("unsigned values cannot be negated") which will be confusing to debug when you're just trying to find a midpoint between two numbers. What I don't quite understand is why the opposite (`-20.mid(&0b10u64)`) still errors out with the same exact "unsigned values cannot be negated" error. Why is the unsigned and not the -20 taking prececence here? Doing `-20i64.mid(&0b10u64)` I get the expected error: "expected `&i64`, found `&u64`."
mmastrac 2y ago
Style nits: this would be much better with an enum Return: enum Found { Empty, Before(T), After(T), Between(T, T), } ... and a range parameter instead of L and R. And, TBH, this should probably just panic! on an invalid predicate rather than returning an error. Programming errors should panic.
- ChadNauseam 2y ago
  All good points, thank you. A range parameter would be especially good because I think you could use RangeInclusive to emphasize that it’s an inclusive range which is not obvious from the type signature.
dmitrygr 2y ago
Oh god. A trait to average two numbers? As a separate function that nobody will ever find in a larger codebase since it can live anywhere? I am yet again convinced that C is better. Thanks.
- Ygg2 2y ago
  Not two numbers. Two somethings. It can average colors, sounds, etc.
  - dmitrygr 2y ago
    Rust ... for when you need to binary search colors C ... for ... sane tings?
amjoshuamichael 2y ago
Wow, this binary search implementation is sure to reduce code duplication. It's so elegant! Can I try?! Here's my implementation of a rust program that can do anything! ``` pub trait Program<T> { pub fn run(self); } pub fn run_program<T: Program>(program: T) { program.run(); } ``` Boom. Just look at the code. How could it be simpler? This works for any struct that implements the `Program` trait. /s While the code in the original post is elegant, and cool from a "hey look what i can do!" perspective, I really feel like at some point we lost the plot on templates with Rust. When you try to finagle an implementation of a general algorithm, you just end up with a solution that works poorly in all cases, instead of one that works well in most cases. I've written a lot of Rust, and I definitely know what it's like to get high off of your own template fumes. I once wrote a function with five generics and two trait constraints and I thought it was the coolest shit I'd ever done. But really, I could have just written, like, three discrete functions, and it would have been clearer and smaller. If someone used something with binary search algorithm other than the Mid implementation shown in the post, that would categorically be bad code from someone who was trying to be too clever. If someone has a unique binary search to do, they should write it themselves. That way, the whole algorithm will be on display, and it will be easier to see ways to make it simpler or improve it in the context of the unique search operation. Also, it will be much clearer. https://en.wiktionary.org/wiki/thneed https://en.wiktionary.org/wiki/thneed
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 } } } } }
cranky908canuck 2y ago
I really like Rust, and what it enables, but this seems like a wonderful counterexample. For a practical programmer, bsearch is on a sorted array. Implement that, with the necessary type abstractions. So: build the objects into an array of references, sort that, then bsearch it already. If you need to keep that array around, do that. Way easier to look at the code and be reasonably confident that it's ok. Anything else is fobbing off the abstractions to something not-nearly-obvious ( eg, a 'Mid' trait?). I disagree that this is a defect in Rust. But I suppose that enabling this kind of misabstraction may indeed be a defect in Rust. Sound an awful lot like Fermat: "the truly marvellous proof which the margin is too narrow to contain".

59 points by ChadNauseam 2y ago

gnuvince 2y ago

> Just look at the code. How could it be simpler? Cannot tell if this is a joke.

Aeolos 2y ago
Which part do you find complicated? The code itself looks very straightforward, two preconditions and a loop. I don't see any significant difference in terms of complexity compared to any other low-level systems programming language. It's obviously a bit more verbose than python or haskell, but those are not targeting the same audience.
IshKebab 2y ago
It looks extremely simple to me. I definitely have never seen a simpler binary search implementation (though in fairness it punts the midpoint calculation). Why do you think it's a joke?
johnisgood 2y ago
Yeah, Perl is simple, too, then.

IncreasePosts 2y ago

> This one also makes that assumption, but in some cases if that assumption is violated it returns an error rather than silently returning a meaningless Sometimes returning an error and sometimes returning an incorrect value doesn't sound like a binary search that is "absolutely reliable". Also, s/consolation/consultation/

edflsafoiewq 2y ago
It doesn't seem possible to determine if the predicate is monotonic without doing a full scan, thus not being a binary search.
fallingsquirrel 2y ago
It seems to me that it's impossible for a binary search to detect all errors. The precondition is that the list must be sorted, and to fully verify that assumption would be O(n). That would make your binary search no better than a linear search. So I can forgive the best-effort error checking.
- ratmice 2y ago
  In theory at least that precondition could be guaranteed by a newtype like SortedList without requiring any linear scan, that would work at least for most cases where lists are sorted by an algorithm. Though not necessarily custom data which is constructed sorted/maintains it's sorting outside the algorithm, but you could perhaps have an unsafe constructor for your SortedList type. That should avoid a linear scan...
- _proofs 2y ago
  i am not sure i see a use case where that precondition is anything but mandatory (and at least a requirement in app space for the related data), if youre intending on making practical use of the algo. if theres a risk that your input is unstable in ordering, then reaching for bsearch seems like a "premature optimization", and youd be better off with a straightforward linear scan until requirements (or your kanguage of choice's bst/heap/rbt equivalent), or data is preprocessed upstream in a way that makes sense for the contexts wanting to use it.
Almondsetat 2y ago
Binary search only works if you suppose the data is well structured. If you perform the search and in the meantime you spot a passing inconsistency, you can interrupt everything and throw an error. But other than that, checking the entire structure negates the entire point of the algorithm
deleted 2y ago
[deleted]

deleted 2y ago

[deleted]

eknkc 2y ago

While the implementation is straightforward enough, this post clearly shows me why I don’t like Rust. So, the function accepts two values that implement Mid trait. And there is a blanket implementation for Mid that applies to anything can be added, substracted, divided etc and can be derived from a u8. So now this will make every numeric type a Mid. (Which, as the author states only an example I guess) I can read and understand how this works here. But when I’m in a larger code base, I can not find what trait implementation made what possible. With all the trait bounds and implicit conversions happening around and macros implementing traits on stuff it becomes a shit stew in a hurry. And everyone always reaches to the most clever way to do things. I mean, does Mid need to be a trait? I guess it works beautifully yeah. I’d prefer to pass a midpoint calculator function instead. I guess this turned into a rant. I actually really like Rust the language but I think I don’t like Rust codebases basically. It is the least readable language I’ve seen not because of the syntax but because of all the cleverness going on around the traits and macros.

worik 2y ago
> I actually really like Rust the language but I think I don’t like Rust codebases basically. And > everyone always reaches to the most clever way to do things. Yes oh yes Rust was a brilliant idea spoilt by too much cleverness I'm hoping for Rust II. A smaller language, with a bigger standard library and no dependence on run times. By "no dependence on run times." I mean no async/await. It is an abomination in Rust
- Conscat 2y ago
  There already exist many affine-typed languages with fewer features than Rust. When you phrase it like "Rust but with weaker type safety and higher-overhead abstractions" one might see why this premise fails to gain much traction, though.
- aw1621107 2y ago
  > By "no dependence on run times." I mean no async/await. It is an abomination in Rust Out of curiosity, what alternative would you have preferred to see, if any?

rurban 2y ago

You can omit the runtime sorted checks via proper types. Only accept sorted arrays or lists, and enforce them with such a class. This would make it convenient, faster and safer. It would also take the sort check from the object, and not as extra argument.

im3w1l 2y ago
In theory I like this, but it raises the question of how it would work in practice; in practice people create non-sorted lists and then sort them in-place. Maybe you could have the sort method return a sorted-token that certifies that a given array is sorted. And the token would read-only borrow the array, to ensure no one can modify the array as long as the token is valid. Is it even possible for a rust function to take a mutable borrow as a parameter, decay it to an immutable borrow and store that somewhere, such that other people can borrow the parameter after the function has returned?
- aw1621107 2y ago
  > Is it even possible for a rust function to take a mutable borrow as a parameter, decay it to an immutable borrow and store that somewhere, such that other people can borrow the parameter after the function has returned? I think it's possible under some scenarios with the appropriate lifetimes? For example, https://rust.godbolt.org/z/6fe8c4sf4 https://rust.godbolt.org/z/6fe8c4sf4: struct Magic<'a> { reference: &'a i32 } impl<'a> Magic<'a> { fn new<'b: 'a>(source: &'b mut i32) -> Magic<'a> { Magic { reference: source } } } fn double(i: &i32) -> i32 { i * 2 } fn main() { let mut i = 0; let m = Magic::new(&mut i); double(m.reference); } I think this will stop working once the compiler can no longer see that the lifetimes work out, but I think that makes sense - there's a mutable object underlying the mutable borrow, and the compiler needs to verify that no one else can get another mutable borrow while the derived immutable borrows are live.
  - im3w1l 2y ago
    So let's for completenes circle back to the usecase of a certified sorted array, it would be something like this struct Sorted<'a> { reference: &'a [i32] } impl<'a> Sorted<'a> { fn in_place<'b: 'a>(source: &'b mut [i32]) -> Sorted<'a> { source.sort(); Sorted { reference: source } } } fn use_sorted_array(sorted_arr: &Sorted) { let arr = sorted_arr.reference; println!("{} {} {}", arr[0], arr[1], arr[2]); } fn main() { let mut arr = [2, 3, 1]; let sorted_arr = Sorted::in_place(&mut arr); use_sorted_array(&sorted_arr); } You might also want to add methods on Sorted for creating a Option<Sorted> by verifying the sortedness of an immutable reference and a method that copies an array and sorts it (it would need to return a struct of a Box for managing the lifetime and a Sorted pointing into the box, or something I guess, probably need to use Pin?) --- On a completely separate note, this will actually not work for the binary search in the article in question, as it uses binary search on a predicate. Having a sorted array doesn't guarantee that the predicate will be monotonic.

re 2y ago

> You want one that doesn't require a consolation with a manual to remember if it returns the first value that's greater or the last value that's lower. ... No more needing to remember "does this return the highest index whose value is lower than the value I'm searching for, or the lowest index whose value is greater than the value I'm searching for?". This one returns both, so you can use whichever you need for your use case. This (italicized part) feels like a weird requirement. Function/API documentation (which this author's code lacks) is important, and I don't think I ever write a call to an unfamiliar function without checking the docs for it. Assuming that you know what a function does based on the name alone is a recipe for buggy code. This is also a kind of unusual formulation of binary search which searches across a monotonic function space rather than a sequence. I get that this is more general and can be used to implement the latter, but a less general interface that only works on sequences is IMO more intuitive: in that case, I expect it to return either the index of the target number, or the index where it should be inserted if not found. It's somewhat telling that the author doesn't offer any code examples demonstrating how to use this wonderful general function to solve the common use case of finding an element in a sorted vector, or inserting a new one into the correct location.

edflsafoiewq 2y ago
The interface is nicer for keyframe interpolation eg. the problem where you have a list of (X,Y) pairs and you want to find the two pairs that straddle a given x and interpolate between them. In that case, search(|&i| v[i].0 >= x, 0, v.len() - 1) handles the three cases "before the beginning", "after the end", and "between two pairs" fairly naturally.

leni536 2y ago

> The only case where it returns (None, None) are those when it detects non-monotonicity in your predicate (returning false when a lower input returned true). So if you know your predicate is monotonic, feel free to hit this case with a panic!("should never happen"). Empty range?

edflsafoiewq 2y ago
No such thing, the range is inclusive of the l and r endpoints.

orlp 2y ago

This binary search is pretty bad in my opinion. Some issues: 1. It doesn't support the empty array, because l and r are both inclusive. 2. It performs way more predicate tests than necessary. 3. An incorrectly implemented Mid trait causes a silent infinite loop. 4. If a fundamental programming error in the sanity check is detected it just silently returns Nones instead of panicking.

ramon156 2y ago
3 is not a good reason. i It's the developer's job to not screw up. What's the alternative?
- orlp 2y ago
  I would normally agree, but the author went out of their way to check for error conditions in their binary search. I think a silent infinite loop is antithetical to that.
- gpm 2y ago
  This is a case where less abstraction would make the bug a lot more obvious. Binary search is simple enough that I don't think a generic implementation of it is worth introducing the possibilities of errors at a distance like that one.
- deleted 2y ago
  [deleted]
bqmjjx0kac 2y ago
5) The provided Mid implementation will panic for signed integer types. There's a part where it sorts `self` and `other`, then subtracts. let difference = *large - *small; Suppose large is 0 and small is i32::MIN. Kaboom, right? For reference: https://github.com/dfinity/ic/commit/79aca8ede9fccd322e0e01183ee72c0bc3ed2e61#diff-41cafdf6b2a805c65ef8163a866c3924a49b2487d6588dda414cfd42005cc44cR19 https://github.com/dfinity/ic/commit/79aca8ede9fccd322e0e011...
dvt 2y ago
Agree with basically everything here, plus I would add that this method also has weird ergonomics. For example there is technically a midpoint between these two: `0b10u64.mid(&-20)`--but you get a weird compiler error ("unsigned values cannot be negated") which will be confusing to debug when you're just trying to find a midpoint between two numbers. What I don't quite understand is why the opposite (`-20.mid(&0b10u64)`) still errors out with the same exact "unsigned values cannot be negated" error. Why is the unsigned and not the -20 taking prececence here? Doing `-20i64.mid(&0b10u64)` I get the expected error: "expected `&i64`, found `&u64`."

mmastrac 2y ago

Style nits: this would be much better with an enum Return: enum Found { Empty, Before(T), After(T), Between(T, T), } ... and a range parameter instead of L and R. And, TBH, this should probably just panic! on an invalid predicate rather than returning an error. Programming errors should panic.

ChadNauseam 2y ago
All good points, thank you. A range parameter would be especially good because I think you could use RangeInclusive to emphasize that it’s an inclusive range which is not obvious from the type signature.

dmitrygr 2y ago

Oh god. A trait to average two numbers? As a separate function that nobody will ever find in a larger codebase since it can live anywhere? I am yet again convinced that C is better. Thanks.

Ygg2 2y ago
Not two numbers. Two somethings. It can average colors, sounds, etc.
- dmitrygr 2y ago
  Rust ... for when you need to binary search colors C ... for ... sane tings?

amjoshuamichael 2y ago

Wow, this binary search implementation is sure to reduce code duplication. It's so elegant! Can I try?! Here's my implementation of a rust program that can do anything! ``` pub trait Program<T> { pub fn run(self); } pub fn run_program<T: Program>(program: T) { program.run(); } ``` Boom. Just look at the code. How could it be simpler? This works for any struct that implements the `Program` trait. /s While the code in the original post is elegant, and cool from a "hey look what i can do!" perspective, I really feel like at some point we lost the plot on templates with Rust. When you try to finagle an implementation of a general algorithm, you just end up with a solution that works poorly in all cases, instead of one that works well in most cases. I've written a lot of Rust, and I definitely know what it's like to get high off of your own template fumes. I once wrote a function with five generics and two trait constraints and I thought it was the coolest shit I'd ever done. But really, I could have just written, like, three discrete functions, and it would have been clearer and smaller. If someone used something with binary search algorithm other than the Mid implementation shown in the post, that would categorically be bad code from someone who was trying to be too clever. If someone has a unique binary search to do, they should write it themselves. That way, the whole algorithm will be on display, and it will be easier to see ways to make it simpler or improve it in the context of the unique search operation. Also, it will be much clearer. https://en.wiktionary.org/wiki/thneed https://en.wiktionary.org/wiki/thneed

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 } } } } }

cranky908canuck 2y ago

I really like Rust, and what it enables, but this seems like a wonderful counterexample. For a practical programmer, bsearch is on a sorted array. Implement that, with the necessary type abstractions. So: build the objects into an array of references, sort that, then bsearch it already. If you need to keep that array around, do that. Way easier to look at the code and be reasonably confident that it's ok. Anything else is fobbing off the abstractions to something not-nearly-obvious ( eg, a 'Mid' trait?). I disagree that this is a defect in Rust. But I suppose that enabling this kind of misabstraction may indeed be a defect in Rust. Sound an awful lot like Fermat: "the truly marvellous proof which the margin is too narrow to contain".