That's really cool - would you care to post some example code so we can see the ...

gjm11 · on Jan 31, 2012

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 · on Jan 31, 2012

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 · on Jan 31, 2012

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.