5 ms·

int mid =(low + high) / 2; > Specifically, it fails if the sum of low and high is greater than the maximum positive int value (2^31 - 1). I would really chall

int mid =(low + high) / 2; > Specifically, it fails if the sum of low and high is greater than the maximum positive int value (2^31 - 1). I would really challenge calling this kind of effects "bug" or "breakage". It's like calling Newtons law of gravity broken, because it's not accurate at predicting how galaxies move. Things are engieered and tested for a certain scale. Knowing which tools to use at which sacle is part of the craft of engineering.

secondcoming 2y ago
I would disagree. The inputs to these functions are user controlled and so can be forced to break, whereas humans cannot change how gravity works.
- deleted 2y ago
  [deleted]
- dzaima 2y ago
  But in what realistic scenario would a user be able to put in ≥2^31 while not being able to put in 2^32-1 (which probably breaks many more things from innocent increments or similar) or 2^100?
  - Retric 2y ago
    And further this all assumes they used int vs. long. It can be “wrong” in that it only works for arrays of under 2^63 elements without that ever being a possibility. Production code is often filled with edge case bugs that simply never come up. Works for 100x the expected use case is generally good enough if you’re approaching the limits where 2^31 is a potential issue then you are also approaching the case where 2^32 definitely will be.
  - sillysaurusx 2y ago
    Hacking, of course. Overflows are one of the primary ways that hackers gain control of systems.
    - Retric 2y ago
      That’s irrelevant for majority of software.
      - sillysaurusx 2y ago
        This mindset is why hackers are able to exploit most systems.
        Retric 2y ago
        Which isn’t a problem as exploiting most software is meaningless. Wow someone can hack software they already have root access to the machine for whatever will we do. It’s management and developers not treating software where it is meaningful for someone to hack as a different category that’s an actual problem.
        javcasas 2y ago
        So a coworker sends me this CAD file via email, I open it and my computer gets controlled by a botnet, and the file immediately sends itself to all my outlook contacts. Nah, that sounds impossible. I'm sure it has never ever happened.
        Retric 2y ago
        Opening 3rd party files is one of those risks I was just talking about. There’s a user moving around in a game, and there’s opening a workplace file these are inherently different kinds of risks. If your building a flappy bird clone you can know exactly how it’s going to interact with the world.
  - wat10000 2y ago
    2^32-1 is almost always a possibility when 2^32 is, but there are many cases where those are possible but 2^100 is not. Basically anything where the value is a count of something rather than raw input fits the bill. How many characters, lines, or files do you support? 2^32 is a totally feasible number in many contexts. 2^100 is physically impossible, there isn’t enough matter.
    - dzaima 2y ago
      If you accept 2^32, then code using 32-bit ints is definitely broken on it and thus the OP question of the issue on half that is irrelevant. Which is my point - widening the acceptable input range from 2^31 to 2^32 (or in the case of signed integers, from 2^30 to 2^31; give or take 1 of course) just "fixes" one small case of the actual core issue of nearly any arithmetic anywhere being wrong if you don't explicitly constrain input sizes.
      - wat10000 2y ago
        I agree on there not being much difference between 2^30/31/32. But it’s not “nearly any arithmetic.” If your size is an actual data size, then 2^64 is fine.
        dzaima 2y ago
        Right, with 64-bit ints things are a lot nicer. Though you can still run into some issues on "generate this much data" tasks as opposed to "operate over existing data of this size", though perhaps less exploitably so.
ajuc 2y ago
The problem is that it's not that much harder to make it work for all the valid inputs. Not doing that is not good enough. Another example is summing lots of floats naively instead of using Kahan's algorithm. It's like we had a theory of gravity that doesn't work on Mars because we have unnecessary division by (m-Mars' mass) in our laws :) It wouldn't be good physics.
- croemer 2y ago
  Nice example with the 1/(m-m_mars)!
- xigoi 2y ago
  Is it worth making the algorithm slower just to have it work on extreme edge cases?
  - javcasas 2y ago
    Is it worth to make the algorithm faster at the cost of throwing surprise OutOfBounds exceptions in some extreme edge cases? Maybe, but only if you - and only you,and not an attacker can control the case you are in.
    - xigoi 2y ago
      If an attacker can somehow make sure that there is an array with 2³⁰ elements, you have worse problems than a binary search crashing.
      - javcasas 2y ago
        Why do you think this algorithm only applies to arrays? Why do you think this algorithm doesn't apply to this sine lookup table that the compiler placed at the end of the memory in the microcontroller?
        deleted 2y ago
        [deleted]
alanfranz 2y ago
> certain scale Make it explicit. If the array is too large, throw an IllegalArgumentException. Document the limit. Then I agree with you. Otherwise, if an allowed input crashes the program at runtime with a random exception, I respectfully disagree.
- brabel 2y ago
  Then you should absolutely stay away from C :)
  - jldugger 2y ago
    Words to live by!
  - alanfranz 2y ago
    I do. But the example was Java.
- feoren 2y ago
  IllegalArgumentException is OK in your book, but OverflowException is not? It's very rare that I actually care which exception type is thrown, but it's a little more polite to throw more clear and reliable exception types. But saying "this could be a little more polite and therefore YOUR CODE HAS A BUG" would make me never want to work with you again.
  - alanfranz 2y ago
    Explict OverflowException could be ok but it may not tell me the root cause. A random index error is not ok at any time.
perching_aix 2y ago
These implementations are definitely broken when the specification goes like "you just pass in your array here and it will perform binary search on it for your value." Yes, you could constrain this spec, but come on... It's such a blatant example for a bug, that I struggle to believe how can anyone even remotely conceive and pivot to the idea that "nuh-uh, this is a bad spec not a bad implementation!".
wat10000 2y ago
Sometimes they’re engineered and tested for a certain scale. More often they’re engineered and tested for an arbitrary scale. The limits aren’t considered, behavior at the edges isn’t accounted for, and it’s assumed it will be good enough for real world inputs. The use of `int` tends to be a dead giveaway. There are some cases where it’s clearly correct: where the spec says so (like argv), where you’re starting from a smaller type and it’s impossible for the calculations to overflow in an int (like adding two uint8), that sort of thing. And there are cases where it’s subtly correct, because you know the range of the value is sufficiently limited, either by mechanics or by spec. But most of the time, int gets chosen because it’s the apparent default and it’s easy to type. No analysis has been done to see if it’s correct or if you want to declare your code to only support inputs in a certain range. It’s really clear if you’ve written a binary search (or anything else that works on general arrays) in C and you use int as the index type. There’s pretty much no scenario where that makes sense. In theory you could analyze the entire program and prove that over-large arrays are never passed in, and keep doing it to make sure it stays that way, but that’s not realistic. If the programmer actually took one second to think about the appropriate data types, they’d use size_t rather than int. You can still have this bug with size_t, of course. But it won’t be “this falls apart with arrays over 1G elements on 64-bit systems that can easily handle them.” If you declare that you wrote the obvious midpoint calculation with size_t because you didn’t intend to support byte arrays larger than half the address space, it’s at least plausible.
- tehjoker 2y ago
  i write c++, but i had to teach myself and always wondered why others use imprecise types. portability is one possibility, but then you can't know if your datastructure will break for a given input
  - wat10000 2y ago
    History and tradition at this point. Bit-sized integers and the other “meaningful” integer types like size_t weren’t added to the languages themselves until C99 and C++11. A lot of us learned those languages before that, and lots of code still exists from that time, or at least code bases that have evolved from that time. I think it actually comes from the opposite of portability. Access to different kinds of systems wasn’t common then. If you were learning and working on a system where int is 32 bits and pointers are 32 bits, and other possibilities are just vague mentions in whatever books you’re learning from, it’s very easy to get into the habit of thinking that int is the right type for a 32-bit quantity and for something that can hold a pointer.
javcasas 2y ago
> Certain scale Or just put the algorithm in a 16-bit microcontroller, put some table that needs to be looked up (think precomputed sine table), put that table near the end of the memory range, and just make the mistake to call binary search specifying the start and end memory positions of the table.

secondcoming 2y ago

I would disagree. The inputs to these functions are user controlled and so can be forced to break, whereas humans cannot change how gravity works.

deleted 2y ago
[deleted]
dzaima 2y ago
But in what realistic scenario would a user be able to put in ≥2^31 while not being able to put in 2^32-1 (which probably breaks many more things from innocent increments or similar) or 2^100?
- Retric 2y ago
  And further this all assumes they used int vs. long. It can be “wrong” in that it only works for arrays of under 2^63 elements without that ever being a possibility. Production code is often filled with edge case bugs that simply never come up. Works for 100x the expected use case is generally good enough if you’re approaching the limits where 2^31 is a potential issue then you are also approaching the case where 2^32 definitely will be.
- sillysaurusx 2y ago
  Hacking, of course. Overflows are one of the primary ways that hackers gain control of systems.
  - Retric 2y ago
    That’s irrelevant for majority of software.
    - sillysaurusx 2y ago
      This mindset is why hackers are able to exploit most systems.
      - Retric 2y ago
        Which isn’t a problem as exploiting most software is meaningless. Wow someone can hack software they already have root access to the machine for whatever will we do. It’s management and developers not treating software where it is meaningful for someone to hack as a different category that’s an actual problem.
        javcasas 2y ago
        So a coworker sends me this CAD file via email, I open it and my computer gets controlled by a botnet, and the file immediately sends itself to all my outlook contacts. Nah, that sounds impossible. I'm sure it has never ever happened.
        Retric 2y ago
        Opening 3rd party files is one of those risks I was just talking about. There’s a user moving around in a game, and there’s opening a workplace file these are inherently different kinds of risks. If your building a flappy bird clone you can know exactly how it’s going to interact with the world.
- wat10000 2y ago
  2^32-1 is almost always a possibility when 2^32 is, but there are many cases where those are possible but 2^100 is not. Basically anything where the value is a count of something rather than raw input fits the bill. How many characters, lines, or files do you support? 2^32 is a totally feasible number in many contexts. 2^100 is physically impossible, there isn’t enough matter.
  - dzaima 2y ago
    If you accept 2^32, then code using 32-bit ints is definitely broken on it and thus the OP question of the issue on half that is irrelevant. Which is my point - widening the acceptable input range from 2^31 to 2^32 (or in the case of signed integers, from 2^30 to 2^31; give or take 1 of course) just "fixes" one small case of the actual core issue of nearly any arithmetic anywhere being wrong if you don't explicitly constrain input sizes.
    - wat10000 2y ago
      I agree on there not being much difference between 2^30/31/32. But it’s not “nearly any arithmetic.” If your size is an actual data size, then 2^64 is fine.
      - dzaima 2y ago
        Right, with 64-bit ints things are a lot nicer. Though you can still run into some issues on "generate this much data" tasks as opposed to "operate over existing data of this size", though perhaps less exploitably so.

ajuc 2y ago

The problem is that it's not that much harder to make it work for all the valid inputs. Not doing that is not good enough. Another example is summing lots of floats naively instead of using Kahan's algorithm. It's like we had a theory of gravity that doesn't work on Mars because we have unnecessary division by (m-Mars' mass) in our laws :) It wouldn't be good physics.

croemer 2y ago
Nice example with the 1/(m-m_mars)!
xigoi 2y ago
Is it worth making the algorithm slower just to have it work on extreme edge cases?
- javcasas 2y ago
  Is it worth to make the algorithm faster at the cost of throwing surprise OutOfBounds exceptions in some extreme edge cases? Maybe, but only if you - and only you,and not an attacker can control the case you are in.
  - xigoi 2y ago
    If an attacker can somehow make sure that there is an array with 2³⁰ elements, you have worse problems than a binary search crashing.
    - javcasas 2y ago
      Why do you think this algorithm only applies to arrays? Why do you think this algorithm doesn't apply to this sine lookup table that the compiler placed at the end of the memory in the microcontroller?
      - deleted 2y ago
        [deleted]

alanfranz 2y ago

> certain scale Make it explicit. If the array is too large, throw an IllegalArgumentException. Document the limit. Then I agree with you. Otherwise, if an allowed input crashes the program at runtime with a random exception, I respectfully disagree.

brabel 2y ago
Then you should absolutely stay away from C :)
- jldugger 2y ago
  Words to live by!
- alanfranz 2y ago
  I do. But the example was Java.
feoren 2y ago
IllegalArgumentException is OK in your book, but OverflowException is not? It's very rare that I actually care which exception type is thrown, but it's a little more polite to throw more clear and reliable exception types. But saying "this could be a little more polite and therefore YOUR CODE HAS A BUG" would make me never want to work with you again.
- alanfranz 2y ago
  Explict OverflowException could be ok but it may not tell me the root cause. A random index error is not ok at any time.

perching_aix 2y ago

These implementations are definitely broken when the specification goes like "you just pass in your array here and it will perform binary search on it for your value." Yes, you could constrain this spec, but come on... It's such a blatant example for a bug, that I struggle to believe how can anyone even remotely conceive and pivot to the idea that "nuh-uh, this is a bad spec not a bad implementation!".

wat10000 2y ago

Sometimes they’re engineered and tested for a certain scale. More often they’re engineered and tested for an arbitrary scale. The limits aren’t considered, behavior at the edges isn’t accounted for, and it’s assumed it will be good enough for real world inputs. The use of `int` tends to be a dead giveaway. There are some cases where it’s clearly correct: where the spec says so (like argv), where you’re starting from a smaller type and it’s impossible for the calculations to overflow in an int (like adding two uint8), that sort of thing. And there are cases where it’s subtly correct, because you know the range of the value is sufficiently limited, either by mechanics or by spec. But most of the time, int gets chosen because it’s the apparent default and it’s easy to type. No analysis has been done to see if it’s correct or if you want to declare your code to only support inputs in a certain range. It’s really clear if you’ve written a binary search (or anything else that works on general arrays) in C and you use int as the index type. There’s pretty much no scenario where that makes sense. In theory you could analyze the entire program and prove that over-large arrays are never passed in, and keep doing it to make sure it stays that way, but that’s not realistic. If the programmer actually took one second to think about the appropriate data types, they’d use size_t rather than int. You can still have this bug with size_t, of course. But it won’t be “this falls apart with arrays over 1G elements on 64-bit systems that can easily handle them.” If you declare that you wrote the obvious midpoint calculation with size_t because you didn’t intend to support byte arrays larger than half the address space, it’s at least plausible.

tehjoker 2y ago
i write c++, but i had to teach myself and always wondered why others use imprecise types. portability is one possibility, but then you can't know if your datastructure will break for a given input
- wat10000 2y ago
  History and tradition at this point. Bit-sized integers and the other “meaningful” integer types like size_t weren’t added to the languages themselves until C99 and C++11. A lot of us learned those languages before that, and lots of code still exists from that time, or at least code bases that have evolved from that time. I think it actually comes from the opposite of portability. Access to different kinds of systems wasn’t common then. If you were learning and working on a system where int is 32 bits and pointers are 32 bits, and other possibilities are just vague mentions in whatever books you’re learning from, it’s very easy to get into the habit of thinking that int is the right type for a 32-bit quantity and for something that can hold a pointer.

javcasas 2y ago

> Certain scale Or just put the algorithm in a 16-bit microcontroller, put some table that needs to be looked up (think precomputed sine table), put that table near the end of the memory range, and just make the mistake to call binary search specifying the start and end memory positions of the table.