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

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.