Why does my binary search need an extra comparison? log2(N)+1

I want to find the index of the first integer in an array of integers which is <= key. I can do it with binary search in log2(N)+1 compares. Shouldn’t it be possible with only log2(N) compares?

// Returns the index of the first integer in keys <= key. size must be a power of 2.
unsigned find(int key, int* keys, unsigned size) {    
    int* origKeys = keys;

    for (int i = 0; i < log2(size); i++) {
        size /= 2;

        if (keys[size] < key)
            keys += size;
    }

    unsigned i = unsigned(keys - origKeys);
    // Not only is this step messy, because it doesn't fit the loop, but
    // now we have log2(n) + 1 comparisons.
    if (*keys < key)
        i++;

    return i;
}

You need to sign in to view this answers