3 ms·
You mean this one? int binary_search_pow2(const int a[], int len, int key) { int i = 0, step; for (step = len / 2; step > 0; step >>= 1)
by gsg 15y ago
You mean this one?
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.
- sesqu 15y agoI 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; }