8 ms·

Nearly all binary search and merge sort implementations are broken (2006)

148 points by arto 15y ago

willvarfar 15y ago
an old story but still well worth the re-reading
pantaloons 15y ago
I'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 <= UINT_MAX < 2 * INT_MAX, which is valid in C99 for INT_MAX >= 65535.)
- caf 15y ago
  INT_MAX == UINT_MAX is the only valid failing case, because elsewhere in the standard integer types are restricted to pure binary representations. This means that if UINT_MAX is greater than INT_MAX, it must be at least INT_MAX * 2 + 1.
  - pantaloons 15y ago
    That can't actually be taken for granted, relevant Usenet discussion begins here: http://groups.google.com/group/comp.std.c/browse_thread/thread/6f1c599324bb2c2e/cd31b3e5003c45f9 http://groups.google.com/group/comp.std.c/browse_thread/thre...
    - caf 15y ago
      I concur with Dan Pop's interpretation.
tbrownaw 15y ago
This 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"?
- emillon 15y ago
  You can also substract two pointers (this is defined only if the two pointers are within a common memory area). The result is a ptrdiff_t which is more or less the scalar version of a void*.
- anorwell 15y ago
  The author is claiming that nearly all binary search implementations are wrong under those specific conditions, not that binary search implementations are wrong under nearly all conditions.
  - tbrownaw 15y ago
    ...bah. I keep forgetting that 64-bit C/C++ compilers are generally LP64 (or even LLP64) instead of ILP64, so "int" being possibly too small is in fact typical. Still. In the example (Java) implicit down-converting isn't allowed, so this is a result of the spec putting arbitrary limits on array size (must be indexed by nonnegative 'int' values). In C or C++ there is no such limit and I think more modern compilers (llvm) will give a warning on loss of precision, so either you have that warning ignored/disabled/unavailable or you have 32-bit code with a billion-element array. I guess what I'm thinking with this is, with a sane language/compiler, the only way to trigger this should be to fill half of your theoretically-logically-addressable memory with an array with single-byte elements.
Wilduck 15y ago
An interesting article that links back to this one: http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ 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.
- finnw 15y ago
  I hope that means "10% get it right first time" and not "only 10% can do it at all, even given a computer and a whole day to do it." Couldn't resist that challenge (although the thread is nearly 2 years old.) I think mine works, at least it gives the right answer for all my test cases.
  - mrich 15y ago
    It's even hard to come up with all the relevant test cases - if you miss a corner case in the implementation, it is likely you will oversee it also in the test case generation. Only an exhaustive search would somehow be able to discover this. With e.g. templates in C++, this is possible in some cases. You can test a template version using the limited range of an unsigned char, while your real implementation will use a uint64. But instead of implementing e.g. a binary search, I prefer to take a proven implementation from e.g. the STL and adapt it for my needs. Experience and programmer lazyness have taught me this is a good way :)
ColinWright 15y ago
Previous, extensive discussion: http://news.ycombinator.com/item?id=1130463 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 http://xlinux.nist.gov/dads/HTML/binarySearch.html And my blog post: http://www.solipsys.co.uk/new/BinarySearchReconsidered.html?HN http://www.solipsys.co.uk/new/BinarySearchReconsidered.html?...
pasbesoin 15y ago
Bypass the borked formatting (original is JS dependent; link below is to Google text-only cache): http://webcache.googleusercontent.com/search?strip=1&q=cache:http%3A%2F%2Fgoogleresearch.blogspot.com%2F2006%2F06%2Fextra-extra-read-all-about-it-nearly.html http://webcache.googleusercontent.com/search?strip=1&q=c... IIRC, this made the rounds a few years ago, in case it sounds familiar.
- justincormack 15y ago
  Thanks. The site is so broken on the ipad, asks if you want a static view which goes to the front page, or an "unsupported" dynamic view which actually turns out to work and is the same page. Google this is so broken! Just make html that works in a browser!
DarkShikari 15y ago
It 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:_Formally_Verified_Design_and_Tested http://en.wikipedia.org/wiki/Evaluation_Assurance_Level#EAL7...
- Bootvis 15y ago
  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?
  - onemoreact 15y ago
    Computer hardware is not correct. So, you need to step past mathematical perfection and write defensively. Rule 1: you can't trust RAM it lies. That said you can build automated tests that add random memory errors to help find the program that's best able to handle memory errors.
    - nickik 15y ago
      You too might be intressted in the link I posted above. Its about building safe hardware (and software), but I don't think its completly safe to anykind of random bit-flips.
    - exDM69 15y ago
      I have never seen a piece of software that is built with memory error tolerance is tested against random memory errors. Have you? Maybe a spacecraft might have some. Error correcting memory, and the software associated with it is, of course, an exception. Is there code dealing with memory errors somewhere in the kernel (of any OS)? For most programming, it would simply not make sense to try to take memory errors into account. It's very unlikely that in the lifetime of the program, there will ever be a situation where a bit will be flipped and it will have an actual effect.
lutorm 15y ago
While 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.
- abecedarius 15y ago
  Yes, the binary search I wrote back in the day used size_t and represented the range as (start, length) rather than (start, end). Full range, and no overflow anywhere if you write it the obvious way. Maybe it was a little bit slower, I don't know. I'd used Bentley as the starting point, so I was surprised when this news first came out and got reported as Bentley's bug. I guess it could be considered so.
- loeg 15y ago
  size_t is actually 32-bit on some 64-bit platforms; you want uint64_t.
  - kragen 15y ago
    If that's true, that's a bug in the platform, not the program. The whole point of size_t is to be however many bits you need to represent the size of things in your address space.
ChuckMcM 15y ago
I'm tempted to solve it with: low/2 + high/2 + (low & high & 1); That side steps the overflow condition completely.
- redthrowaway 15y ago
  It would sidestep the overflow, but prima facie it appears to be slower than the provided: low + (high - low)/2; Your solution takes, depending on the architecture, between several more and nearly double the trips to the ALU. Gimmie a sec; I've got bugger all to do at work. I'll compile it and profile it.
  - ChuckMcM 15y ago
    Would be interested in seeing the profile. Re-ordering it to the following (which the compiler might do too) low&high&1 + low>>1 + high>>1 Should compute in a single cycle if the register coloring is working in the pipeline. The <reg> >> 1 come out of the barrel shifter stage, the low&high&1 resolves in the load, so you end up with a single sum of three operands. Since its being stored in a separate register that would avoid a write stall in the pipeline as well.
finnw 15y ago
Almost the same bug: http://code.google.com/p/guava-libraries/issues/detail?id=616 http://code.google.com/p/guava-libraries/issues/detail?id=61...
tonyg 15y ago
So C, C++, and Java don't have good support for arithmetic. What else is new?
- alexscheelmeyer 15y ago
  +1, this has nothing to do with binary search and everything to do with the fact that almost any application written in those languages will have bugs that do not show until numbers nearing INT_MAX are used. Another given is that all applications that use recursion is bound to run into stack overflow errors/bugs when used on big data.
MarkSweep 15y ago
I don't understand why I need Javscript enabled to merely read a blog post on blogspots.
- sesqu 15y ago
  To be fair, there's a classic version (but the link to it discards the article id, for some unfathomable reason). This works: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html?v=0 http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
jakubw 15y ago
The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code. It surely does if everyone has to write their own binary search implementation when most standard libraries have one and several of them have one that is flexible enough (either due to the language's features or the binary search routine itself) to not just search through a container but through a solution space in an optimization problem. So I'm surprised the author hasn't concluded with the lesson that would be somewhat more practical: It is hard to write even the smallest piece of code correctly, so don't do it and use whatever's in your stack unless you have a good reason not to.
jbarham 15y ago
Nice to see that the Go gets it right: func Search(n int, f func(int) bool) int { // Define f(-1) == false and f(n) == true. // Invariant: f(i-1) == false, f(j) == true. i, j := 0, n for i < j { h := i + (j-i)/2 // avoid overflow when computing h // i ≤ h < j if !f(h) { i = h + 1 // preserves f(i-1) == false } else { j = h // preserves f(j) == true } } // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. return i } http://code.google.com/p/go/source/browse/src/pkg/sort/search.go?name=weekly.2012-01-27#57 http://code.google.com/p/go/source/browse/src/pkg/sort/searc...
- nknight 15y ago
  I expect at least one of the Go authors was well aware of this very incident (the Java breakage), it was fairly well publicized before Go ever saw the light of day.
yason 15y ago
I don't like the index variables and splitting in half part. I like to write my binary searches with bit patterns: 1) figure out the number of bits required to cover the largest index (= a little bit of cheap bit-twiddling) 3) initialize your index to 0 2) flip a bit on in index, starting from the highest bit available from step 1) 3) if data[index] is smaller than what you're looking for, leave the bit on 4) try with the next-lowest bit and loop to 2) until at bit #0 It's pretty easy to write it out in a way that's just obvious, instead of requiring the reader to wrap his mind about which variable is the lowest and highest bound and whether the indexes are inclusive/exclusive in which ends, etc.
- ColinWright 15y ago
  That's really cool - would you care to post some example code so we can see the clarity obtained by this novel approach? Did you come up with it yourself, or did you see it somewhere else?
  - gjm11 15y ago
    I think one of Jon Bentley's "Programming pearls" books contains a version of binary search that works more or less that way and shows how to get there from a naive and more obviously correct implementation by successive small transformations. IIRC it ends up having a particularly tight inner loop. And it doesn't, I think, require a power-of-2-sized array. My copy of the book is at home and I'm at work so I can't check any of my recollections right now.
    - ColinWright 15y ago
      You're right - Programming Pearls, column 8 "Code Tuning." It's not quite like this, and it's in some variant of BASIC, but when you squint, it's there. Thanks.
      - gjm11 15y ago
        You're welcome. In the second edition, which is what I happen to have, it's column 9 (because the old column 4 got split into two) and the code is in a pseudocode that's much more like C with the semicolons deleted than like any version of BASIC. I wasn't quite right to say that the inner loop is very tight; rather, the code assumes a particular size of array and unrolls the loop completely. But, indeed, the size doesn't need to be a power of 2. Here's the (pseudo)code, in case anyone cares. It's for an array of size 1000. I've changed a variable name from "l" to "m" because of the usual l1I| thing. I've removed a couple of helpful comments because anyone who cares enough to bother reading them will probably have more fun figuring everything out on their own. I've also elided some obvious repetitive code and formatted it slightly differently from Bentley. Any errors in the code were probably introduced by me. m = -1 if (x[ 511] < t) m = 1000-512 if (x[m+256] < t) m += 256 if (x[m+128] < t) m += 128 /* ... */ if (x[m+ 2] < t) m += 2 if (x[m+ 1] < t) m += 1 p = m+1 if (p>1000 || x[p]!=t) p = -1 /* i.e., not found */ Bentley says this is "not for the faint of heart". I agree, but I do think it's lovely. Though personally I'd be inclined to use a value of m offset by 1 from what Bentley does (initialize to 0, look up m+255, m+127, etc.) and save a line of code and a couple of cycles.
VMG 15y ago
Why are overflows silent? Shouldn't use cases where you want the overflow behavior be more explicit?

148 points by arto 15y ago

an old story but still well worth the re-reading

I'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 <= UINT_MAX < 2 * INT_MAX, which is valid in C99 for INT_MAX >= 65535.)

caf 15y ago
INT_MAX == UINT_MAX is the only valid failing case, because elsewhere in the standard integer types are restricted to pure binary representations. This means that if UINT_MAX is greater than INT_MAX, it must be at least INT_MAX * 2 + 1.
- pantaloons 15y ago
  That can't actually be taken for granted, relevant Usenet discussion begins here: http://groups.google.com/group/comp.std.c/browse_thread/thread/6f1c599324bb2c2e/cd31b3e5003c45f9 http://groups.google.com/group/comp.std.c/browse_thread/thre...
  - caf 15y ago
    I concur with Dan Pop's interpretation.

tbrownaw 15y ago

This 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"?

emillon 15y ago
You can also substract two pointers (this is defined only if the two pointers are within a common memory area). The result is a ptrdiff_t which is more or less the scalar version of a void*.
anorwell 15y ago
The author is claiming that nearly all binary search implementations are wrong under those specific conditions, not that binary search implementations are wrong under nearly all conditions.
- tbrownaw 15y ago
  ...bah. I keep forgetting that 64-bit C/C++ compilers are generally LP64 (or even LLP64) instead of ILP64, so "int" being possibly too small is in fact typical. Still. In the example (Java) implicit down-converting isn't allowed, so this is a result of the spec putting arbitrary limits on array size (must be indexed by nonnegative 'int' values). In C or C++ there is no such limit and I think more modern compilers (llvm) will give a warning on loss of precision, so either you have that warning ignored/disabled/unavailable or you have 32-bit code with a billion-element array. I guess what I'm thinking with this is, with a sane language/compiler, the only way to trigger this should be to fill half of your theoretically-logically-addressable memory with an array with single-byte elements.

Wilduck 15y ago

An interesting article that links back to this one: http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ 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.

finnw 15y ago
I hope that means "10% get it right first time" and not "only 10% can do it at all, even given a computer and a whole day to do it." Couldn't resist that challenge (although the thread is nearly 2 years old.) I think mine works, at least it gives the right answer for all my test cases.
- mrich 15y ago
  It's even hard to come up with all the relevant test cases - if you miss a corner case in the implementation, it is likely you will oversee it also in the test case generation. Only an exhaustive search would somehow be able to discover this. With e.g. templates in C++, this is possible in some cases. You can test a template version using the limited range of an unsigned char, while your real implementation will use a uint64. But instead of implementing e.g. a binary search, I prefer to take a proven implementation from e.g. the STL and adapt it for my needs. Experience and programmer lazyness have taught me this is a good way :)

ColinWright 15y ago

Previous, extensive discussion: http://news.ycombinator.com/item?id=1130463 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 http://xlinux.nist.gov/dads/HTML/binarySearch.html And my blog post: http://www.solipsys.co.uk/new/BinarySearchReconsidered.html?HN http://www.solipsys.co.uk/new/BinarySearchReconsidered.html?...

pasbesoin 15y ago

Bypass the borked formatting (original is JS dependent; link below is to Google text-only cache): http://webcache.googleusercontent.com/search?strip=1&q=cache:http%3A%2F%2Fgoogleresearch.blogspot.com%2F2006%2F06%2Fextra-extra-read-all-about-it-nearly.html http://webcache.googleusercontent.com/search?strip=1&q=c... IIRC, this made the rounds a few years ago, in case it sounds familiar.

justincormack 15y ago
Thanks. The site is so broken on the ipad, asks if you want a static view which goes to the front page, or an "unsupported" dynamic view which actually turns out to work and is the same page. Google this is so broken! Just make html that works in a browser!

DarkShikari 15y ago

It 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:_Formally_Verified_Design_and_Tested http://en.wikipedia.org/wiki/Evaluation_Assurance_Level#EAL7...

Bootvis 15y ago
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?
- onemoreact 15y ago
  Computer hardware is not correct. So, you need to step past mathematical perfection and write defensively. Rule 1: you can't trust RAM it lies. That said you can build automated tests that add random memory errors to help find the program that's best able to handle memory errors.
  - nickik 15y ago
    You too might be intressted in the link I posted above. Its about building safe hardware (and software), but I don't think its completly safe to anykind of random bit-flips.
  - exDM69 15y ago
    I have never seen a piece of software that is built with memory error tolerance is tested against random memory errors. Have you? Maybe a spacecraft might have some. Error correcting memory, and the software associated with it is, of course, an exception. Is there code dealing with memory errors somewhere in the kernel (of any OS)? For most programming, it would simply not make sense to try to take memory errors into account. It's very unlikely that in the lifetime of the program, there will ever be a situation where a bit will be flipped and it will have an actual effect.

lutorm 15y ago

While 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.

abecedarius 15y ago
Yes, the binary search I wrote back in the day used size_t and represented the range as (start, length) rather than (start, end). Full range, and no overflow anywhere if you write it the obvious way. Maybe it was a little bit slower, I don't know. I'd used Bentley as the starting point, so I was surprised when this news first came out and got reported as Bentley's bug. I guess it could be considered so.
loeg 15y ago
size_t is actually 32-bit on some 64-bit platforms; you want uint64_t.
- kragen 15y ago
  If that's true, that's a bug in the platform, not the program. The whole point of size_t is to be however many bits you need to represent the size of things in your address space.

ChuckMcM 15y ago

I'm tempted to solve it with: low/2 + high/2 + (low & high & 1); That side steps the overflow condition completely.

redthrowaway 15y ago
It would sidestep the overflow, but prima facie it appears to be slower than the provided: low + (high - low)/2; Your solution takes, depending on the architecture, between several more and nearly double the trips to the ALU. Gimmie a sec; I've got bugger all to do at work. I'll compile it and profile it.
- ChuckMcM 15y ago
  Would be interested in seeing the profile. Re-ordering it to the following (which the compiler might do too) low&high&1 + low>>1 + high>>1 Should compute in a single cycle if the register coloring is working in the pipeline. The <reg> >> 1 come out of the barrel shifter stage, the low&high&1 resolves in the load, so you end up with a single sum of three operands. Since its being stored in a separate register that would avoid a write stall in the pipeline as well.

finnw 15y ago

Almost the same bug: http://code.google.com/p/guava-libraries/issues/detail?id=616 http://code.google.com/p/guava-libraries/issues/detail?id=61...

tonyg 15y ago

So C, C++, and Java don't have good support for arithmetic. What else is new?

alexscheelmeyer 15y ago
+1, this has nothing to do with binary search and everything to do with the fact that almost any application written in those languages will have bugs that do not show until numbers nearing INT_MAX are used. Another given is that all applications that use recursion is bound to run into stack overflow errors/bugs when used on big data.

MarkSweep 15y ago

I don't understand why I need Javscript enabled to merely read a blog post on blogspots.

sesqu 15y ago
To be fair, there's a classic version (but the link to it discards the article id, for some unfathomable reason). This works: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html?v=0 http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

jakubw 15y ago

The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code. It surely does if everyone has to write their own binary search implementation when most standard libraries have one and several of them have one that is flexible enough (either due to the language's features or the binary search routine itself) to not just search through a container but through a solution space in an optimization problem. So I'm surprised the author hasn't concluded with the lesson that would be somewhat more practical: It is hard to write even the smallest piece of code correctly, so don't do it and use whatever's in your stack unless you have a good reason not to.

jbarham 15y ago

Nice to see that the Go gets it right: func Search(n int, f func(int) bool) int { // Define f(-1) == false and f(n) == true. // Invariant: f(i-1) == false, f(j) == true. i, j := 0, n for i < j { h := i + (j-i)/2 // avoid overflow when computing h // i ≤ h < j if !f(h) { i = h + 1 // preserves f(i-1) == false } else { j = h // preserves f(j) == true } } // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. return i } http://code.google.com/p/go/source/browse/src/pkg/sort/search.go?name=weekly.2012-01-27#57 http://code.google.com/p/go/source/browse/src/pkg/sort/searc...

nknight 15y ago
I expect at least one of the Go authors was well aware of this very incident (the Java breakage), it was fairly well publicized before Go ever saw the light of day.

yason 15y ago

I don't like the index variables and splitting in half part. I like to write my binary searches with bit patterns: 1) figure out the number of bits required to cover the largest index (= a little bit of cheap bit-twiddling) 3) initialize your index to 0 2) flip a bit on in index, starting from the highest bit available from step 1) 3) if data[index] is smaller than what you're looking for, leave the bit on 4) try with the next-lowest bit and loop to 2) until at bit #0 It's pretty easy to write it out in a way that's just obvious, instead of requiring the reader to wrap his mind about which variable is the lowest and highest bound and whether the indexes are inclusive/exclusive in which ends, etc.

ColinWright 15y ago
That's really cool - would you care to post some example code so we can see the clarity obtained by this novel approach? Did you come up with it yourself, or did you see it somewhere else?
- gjm11 15y ago
  I think one of Jon Bentley's "Programming pearls" books contains a version of binary search that works more or less that way and shows how to get there from a naive and more obviously correct implementation by successive small transformations. IIRC it ends up having a particularly tight inner loop. And it doesn't, I think, require a power-of-2-sized array. My copy of the book is at home and I'm at work so I can't check any of my recollections right now.
  - ColinWright 15y ago
    You're right - Programming Pearls, column 8 "Code Tuning." It's not quite like this, and it's in some variant of BASIC, but when you squint, it's there. Thanks.
    - gjm11 15y ago
      You're welcome. In the second edition, which is what I happen to have, it's column 9 (because the old column 4 got split into two) and the code is in a pseudocode that's much more like C with the semicolons deleted than like any version of BASIC. I wasn't quite right to say that the inner loop is very tight; rather, the code assumes a particular size of array and unrolls the loop completely. But, indeed, the size doesn't need to be a power of 2. Here's the (pseudo)code, in case anyone cares. It's for an array of size 1000. I've changed a variable name from "l" to "m" because of the usual l1I| thing. I've removed a couple of helpful comments because anyone who cares enough to bother reading them will probably have more fun figuring everything out on their own. I've also elided some obvious repetitive code and formatted it slightly differently from Bentley. Any errors in the code were probably introduced by me. m = -1 if (x[ 511] < t) m = 1000-512 if (x[m+256] < t) m += 256 if (x[m+128] < t) m += 128 /* ... */ if (x[m+ 2] < t) m += 2 if (x[m+ 1] < t) m += 1 p = m+1 if (p>1000 || x[p]!=t) p = -1 /* i.e., not found */ Bentley says this is "not for the faint of heart". I agree, but I do think it's lovely. Though personally I'd be inclined to use a value of m offset by 1 from what Bentley does (initialize to 0, look up m+255, m+127, etc.) and save a line of code and a couple of cycles.

VMG 15y ago

Why are overflows silent? Shouldn't use cases where you want the overflow behavior be more explicit?