(low + high) / 2
I mean, that's technically true because it might crash for huge arrays, but if this is a bug then the follow implementation of a function that adds to integers is also buggy, since it will overflow when x + y doesn't fit in an int: int add(int x, int y) { return x + y; }There's nothing about the signature of an ordinary binary search method that would imply that it only works for arrays that have less than MAX_INT/2 elements.
Simply put, in many languages there is no addition operator which does mathematically correct addition and that is a sad state of affairs.
In the first few decades of electronic computers and programming languages, having an addition or any other arithmetic operation that would not signal correctly the overflow exceptions would have been considered as completely unacceptable.
Computers without the right hardware implementation appeared initially among the so-called minicomputers and microcomputers, i.e. the cheapest computers, which initially were intended for things like industrial control or peripherals for larger computers, where it was supposed that competent programmers will take care to use appropriate workarounds for the hardware limitations.
Unfortunately, this kind of implementation of the arithmetic operations, without appropriate means for detecting overflows, intended initially only for the cheapest products, has spread over the years to all CPUs.
Even if from time to time there are news about some horror story caused by a combination of weak hardware with the lack of appropriate software checks, it appears that there is no hope that this unfortunate hardware design fashion will ever be reversed.
I read a book on Clojure when it was fairly new containing a spirited defense of the fact that arithmetic operators like + and - always returned the correct result. This was slower, because they needed to do bounds checking, but the result was always correct. If you wanted faster arithmetic with bugs, you'd use the explicit operators +. or -. (or *. or, presumably, /. -- I'm not sure how division was handled).
Shortly after that, Clojure reversed its policy and + will give you fast addition with bugs.
int add(int x, int y) { return (2*x + 2*y) / 2; }
If ints are 32 bit you would expect to be able to add 1 to 2^20, but that causes an overflow with this implementation. (low + high) / 2 is arguably worse because you turn the algorithm from working on any array into one that only works on arrays that are small enough not to cause the overflow. (low + high) / 2
I use low + (high-low) / 2
to avoid any possible overflow. long add(int x, int y) { return x + y; }
with the caveat of course that `long` is larger than an `int`, which I can't recall if it is valid on all platforms. So mathematical u32 + u32 should be u64, but you can define an `add` function that has strict overflow behavior. return (long)x + y;
to ensure the addition happens after the conversion to long?Simple addition will fail if the result of the expression should fall outside the range of integers expressible for a given integer width—because it can't fit. That's not insightful. It's facile. The criticism of the naive midpoint computation is not facile.
The problem with using `(low + high) / 2` to compute the midpoint (instead of `(high - low) / 2 + low`) is that it will give invalid results even when the data type from the signature is wide enough that the expected result can fit.
On most 64-bit UNIX-like systems, long is the same with long long.
https://www.tbray.org/ongoing/When/200x/2003/03/22/Binary
In an update to his post, Tim linked to Joshua Bloch's "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" post about the problems you describe:
https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
I wonder how many university algorithms engineers would run into a similar situation with. I'm not very far out of university, so I have an unfair advantage, but take some engineers with at least 10 year experience and have them implement Dijkstra's by memory. Not saying this is necessarily a bad thing. If you're in industry for years, you have gained a lot more applicable knowledge to your work, kind of like how runners have a different kind of strength and muscle than weight lifers - they both meet their needs.
That said, I'm surprised at 90% overflowing code. Is it all in that midpoint calculation?
I've written binary search algorithms maybe a half a dozen times, and every time I get tripped up by some boundary condition or other and what is only a few lines of code takes a really long time to get exactly right for all the corner cases.
https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-1...
Covered by HN at the time: https://news.ycombinator.com/item?id=1277459
My own solution was in Python, so it didn't fall prey to the very common integer overflow error. Python has the amazing and handy property that integers don't overflow.
Wikipedia has an entire section dedicated to this here: https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem...