It's the recursion (or parameters to functions in recursion that kills most candidates). It's pretty intuitive in the head.

But I agree, plain vanilla binary search is easy.