Re:Nearly all binary search and merge sort implementations a...
by gsg on Tuesday January 31, 2012 @06:47AM
(#3532847)
You mean this one?
I thought that only worked for power-of-two sized arrays.
[ Parent
| on HN ]
Re:Nearly all binary search and merge sort implementations a...
by sesqu on Tuesday January 31, 2012 @09:38AM
(#3533391)
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;
}