That line from the C/C++ "fix" is an atrocity; `low`, `mid`, and `high` should never have been declared as signed integers in the first place, since array indices are never negative. It's unfortunate that in Java there is no other option than to use signed ints.
Programmer: "The bug is in the choice of data type. Use unsigned ints to index arrays."<p>Computer scientist: "The bug is in the language. Signed integer overflow behavior should have been defined in such a way as to guarantee correct functionality in cases such as this."<p>Me: "Use int64s for this sort of thing. It's still broken, but I'll be retired or dead before anyone notices."<p>Engineer: "The bug is in the documentation. The program is correct but should have been specified for use with element counts no greater than INT_MAX / 2."<p>Mathematician: "A solution exists."<p>Manager: "Ship it."
I'm surprised about the suggested solution for java:<p><pre><code> int mid = (low + high) >>> 1;
</code></pre>
I suppose things like this is why the ">>>" (unsigned shift) operator exists - but it's a bit odd when the value it works on is considered signed by the language, and implemented as two-compliment signed in memory.<p>What's interesting to me is that this allows the sum to overflow, and would fail with the ">>" operator as far as I can tell (signed shift) - just like the original code would fail with simply dividing by 2.<p>Guess it shows java's "system language" roots - in that one might expect there to be a way to be alerted to overflow when working with signed integers - but the solution here is to use a special operator to "fix" the problem.<p>Maybe it's just me, but it's a solution that would feel more at home in assembler, than I personally think it does in java.
So what 'bout this? It's the latest glibc.<p><a href="https://fossies.org/dox/glibc-2.25/stdlib-bsearch_8h_source.html" rel="nofollow">https://fossies.org/dox/glibc-2.25/stdlib-bsearch_8h_source....</a>
> int mid = low + ((high - low) / 2);<p>That may fix things in the case of searching a sorted array, but binary search can be used more generally than that. I think that fix might not work for some of the more general applications of binary search.<p>For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) < 0 and f(b) > 0, and you want to find an n in (a,b), if such n exists, such that f(n) = 0. Binary search on [a, b] is a reasonable approach.<p>If a < 0 and b > 0, then that mid computation could overflow on the subtraction.
I don't think that is broken. The algorithm is sound conceptually. I was almost looking for some type of theory where all mergesorts and binary searches could be improved.
A more modern version of this is: nearly all discussion about sorts that claims computers can't do search in better than O(n log n) are wrong and have been for some time.<p>Edit: I'm quite surprised I'm being modded down given the magnitude of what I'm implying. I suspect someone doesn't understand what I'm saying.
I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit.<p>It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could it be possible to predict?
* for arrays with counts over a billion if you choose to use signed 32-bit integers for array indexes.<p>Not that it isn't a potential problem, but it's a narrow issue.