Oops; you're right. One possible fix is

    for (size_t length = end - begin; length != 1; length = (length + 1) / 2)
    {
        size_t step = length / 2;
        if (compare(begin[step], value))
            begin += step;
    }   
    return begin + compare(*begin, value);

but it admittedly detracts from the simplicity of the former...