my-new-rust-binary-search

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.

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 [2] 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 }
        }
      }
    }
  }

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

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.

Cannot tell if this is a joke.

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".

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/

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.

Empty range?

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.

```

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