Comment by djoldman

I think other responses here may miss an important line of thought.

There seems to be confusion around the differences between bug and correct.

In the referenced study on binary searches, the Google researchers stated that most implementations had bugs AND were "broken" because they did:

    int mid =(low + high) / 2;

And low + high can overflow.

Ostensibly, a proof may require mid to be positive at all times and therefore be invalid because of overflow.

The question is: if we put in assertions everywhere that guarantee correct output, where aborting on overflow is considered correct, then are folks going to say that's correct, or are they going to say oh that's not what binary search is so you haven't implemented it?

EDIT: thinking about it more, it seems that null must be an accepted output of any program due to the impossibility of representing very large numbers.