3 ms·
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 mor
by 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 ago3 is not a good reason. i It's the developer's job to not screw up. What's the alternative?
- orlp 2y agoI 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 agoThis 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 ago5) 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 agoAgree 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`."
- Ygg2 2y agoBecause you can't find midpoint between two different types. One is unsigned other is signed. How would that even work?