Nearly all binary search and merge sort implementations are broken (2006)
googleresearch.blogspot.com
Nearly all binary search and merge sort implementations are broken (2006)
1–10 of 70 posts
Re: Nearly all binary search and merge sort implementations are broken (2006)
#2an old story but still well worth the re-reading
Re: Nearly all binary search and merge sort implementations are broken (2006)
#3I'm tempted to suggest that the fixed C/C++ version is still not correct with respect to this issue, namely on architectures where INT_MAX == UINT_MAX. (Or really INT_MAX = 65535.)
Re: Nearly all binary search and merge sort implementations are broken (2006)
#4This bug requires either (1) low/mid/high are pointers [edit - I don't think this is valid; IIRC pointer arithmetic is only sane for add/subtract an int from a pointer, not divide a pointer or add two pointers]; or (2) item_count > INT_MAX / 2, which means memory_size >= sizeof(your_array) == sizeof(item) * item_count > INT_MAX / 2, which means either 1-byte or 2-byte array elements, or that your ints are smaller than your pointers. So is it really "nearly all"?
Re: Nearly all binary search and merge sort implementations are broken (2006)
#5An interesting article that links back to this one:
http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10...
The claim is that even ignoring overflow, only 10% of programmers can correctly implement a binary search. When I tried it, I thought I got it working, but it was later pointed out that I didn't handle empty lists correctly.
Programming correctly is hard.
Re: Nearly all binary search and merge sort implementations are broken (2006)
#6Previous, extensive discussion: http://news.ycombinator.com/item?id=1130463
I once ran a programming challenge based on this, but I discontinued when I started to get threats of physical violence from people whose code didn't pass the tests.
The Dictionary of Algorithms and Data Structures on the NIST site has a correction I submitted on exactly this point:
http://xlinux.nist.gov/dads/HTML/binarySearch.html
And my blog post: http://www.solipsys.co.uk/new/BinarySearchReconsidered.html?...
Re: Nearly all binary search and merge sort implementations are broken (2006)
#7Bypass the borked formatting (original is JS dependent; link below is to Google text-only cache):
http://webcache.googleusercontent.com/search?strip=1&q=c...
IIRC, this made the rounds a few years ago, in case it sounds familiar.
Re: Nearly all binary search and merge sort implementations are broken (2006)
#8It is not sufficient merely to prove a program correct; you have to test it too. Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible.
This statement is tantamount to saying "you don't merely need to prove Fermat's Last Theorem, you also have to test it for all possible input values". By this line of reasoning, most of mathematics should be thrown out.
If you've proven a program correct, it is correct for all input values, whether you have tested them or not. If your proof ignores complexities such as the range of data values, it isn't a correct proof to begin with. And yes, proving programs correct is often possible -- in fact, the highest levels of software verification actually require explicit proofs of correctness for much of the code; see http://en.wikipedia.org/wiki/Evaluation_Assurance_Level#EAL7...
Re: Nearly all binary search and merge sort implementations are broken (2006)
#9While true, it seems that if your array is that close to the inherent size limit in indexing by ints, this is at most a temporary fix. How fast does your sorting requirements go from 2^31 to 2^32? It seems that you should be using size_t here, not int.
Re: Nearly all binary search and merge sort implementations are broken (2006)
#10It is not sufficient merely to prove a program correct; you have to test it too. Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible. This statement is tantamount to saying "you don't merely need to prove Fermat's Last Theorem, you also have to test it for all possible input values". By this line of reasoning, most of mathematics sho…
You can prove the correctness of a program given a specification of the language you write it in. But is the compiler you use to compile your program correct? Do you know all processor bugs?