binarysearch.c

/* log_2 ceiling */
ALWAYS_INLINE unsigned lb (unsigned long x)
{
        if (x <= 1) return 0;
        return (8*sizeof(unsigned long))-__builtin_clzl(x-1);
}

ALWAYS_INLINE size_t
binary_search (unsigned key, unsigned * vector, size_t size)
{
        unsigned * low = vector;

        for (unsigned i = lb(size); i != 0; i--) {
                size /= 2;
                unsigned mid = low[size];
                if (mid <= key)
                        low += size;
        }

        return (*low > key)? -1: low - vector;
}