Binary search in particular is surprisingly tricky, which is precisely what makes it useful for telling if someone knows how to program. To a significant extent, though, you can cheat by studying binary search itself, which is a surprisingly beautiful thing.
I like this formulation for finding the first index in a half-open range where p is true, assuming p stays true thereafter:
bsearch p i j :=
i if i == j else
bsearch p i m if p m else
bsearch p (m + 1) j
where m := i + (j - i)//2
Or in Python:
def bsearch(p, i, j):
m = i + (j - i) // 2
return (i if i == j
else bsearch(p, i, m) if p(m)
else bsearch(p, m+1, j))
The only tricky thing about this formulation is that m < j if i < j, thus the asymmetric +1 in only one case to ensure progress. If invoked with a p such as a[m] >= k it gives the usual binary search on an array without early termination. The i + (j - i) // 2 formulation is not needed in modern Python, but historically an overflowing (i + j) // 2 was a bug in lots of binary search library functions, notably in Java and C.
(Correction: I said a[m] <= k. This formulation is less tricky than the usual ones, but it's still tricky!)
