The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
The bug is in the author's understanding of his choice of language. The language did a perfectly reasonable thing.
Nearly All Binary Searches and Mergesorts Are Broken (2006)
31–40 of 95 posts
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#32I'm surprised about the suggested solution for java:
int mid = (low + high) >>> 1;
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.
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.
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.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#33A 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.
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.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#34Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#35The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
Big integer by default is a terrible idea. Just look at Python 3.
Could you expand? The number tower is one of the things I happen to like about python 3, but apparently you think there's something wrong? Performance?
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#36A 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. 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.
The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#37> int mid = low + ((high - low) / 2); 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. For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) 0, and you want to find an n in (a,b), if such n exists, such…
In that case, then you can to go back to
int mid = (low + high) / 2;
However, the article specifically talks about merge sort in arrays, so low (your "a") is always >= 0. The discovery was "oh, we went decades before someone had to sort an array with more than 2^31 elements". Frankly, it's akin to when we ran out of IPv4 addresses -- when it was originally built, there was some range over which the computation was defined to be correct, and we later discovered that we wanted to do computation outside that range.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#38Classic programming defect !
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#39A 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. 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.
The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.
Right, but a generalization of discrimination-based sorts didn't exist until earlier this decade. So it was a reasonable statement to misinterpret or relegate to "say you have a 30m character string you wanted to sort as quickly as possible" interview questions.
I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'm still working through the papers, the base of that chain is like 86 pages long!
This search fallacy has been corrected. I'm mentioning one that hasn't.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#40> int mid = low + ((high - low) / 2); 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. For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) 0, and you want to find an n in (a,b), if such n exists, such…
I'm tempted to suggest
(low / 2) + (high / 2)