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.

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

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

> Just look at the code. How could it be simpler?

Cannot tell if this is a joke.

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

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

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.

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.

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

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.

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.

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