I am a huge proponent of "bitwise" binary search. Consider r to be the result index we wish to find in range [0, n), that is, the first index where a predicate returns false, or n if there is no such predicate. We can construct this index bit-by-bit, starting from the most significant bit:

    # Extracts the highest set bit for n > 0.
    # This can be 1-5 instructions on most machines using count leading zeros.
    def highest_bit_set(n):
        return 1 << (n.bit_length() - 1)

    def binary_search(n, predicate):
        # Construct largest possible r such that predicate(r) is true, or 0.
        if n == 0: return 0
        r = 0
        bit = highest_bit_set(n)
        while bit:
            if (r | bit) < n and predicate(r | bit): r |= bit
            bit >>= 1

        # Return smallest possible r such that predicate(r) is false, or n.
        if r > 0 or predicate(0): r += 1
        return r

I find this to be significantly easier to reason about, although I do have a lot of experience with bitwise manipulation. And it is trivial to extend to search a range [lo, hi):

    def binary_search_range(lo, hi, predicate):
        return binary_search(hi - lo, lambda i: predicate(lo + i))

It's similarly trivial to reason they do exactly log2(n) or log2(hi - lo) iterations and are thus worst-case optimal.