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.
int binary_search_pow2(const int a[], int len, int key) {
int i = 0, step;
for (step = len / 2; step > 0; step >>= 1)
if (a[i | step] <= key)
i |= step;
return i;
}
I thought that only worked for power-of-two sized arrays.
I implemented one for practise, without assuming powers of two:
int binarySearch(const int needle, const int haystack[], const int size) {
if (size==0)
return -1;
short log2 = 0; // rounded down
for (int sz=size; sz>>=1; log2++);
int index = 0;
for (int flag=1<<log2; flag>0; flag>>=1) {
index |= flag; // set
if (index>=size || needle<haystack[index])
index ^= flag; // unset
}
return needle==haystack[index] ? index : -index-1;
}
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.
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.
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.
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.