Maybe I was fortunate; I learned how to write a binary search in my lower-level CS courses. I didn't even find it particularly difficult, but then again, the concept was explained quite clearly before I had to code it.
The trick with this binary search test isn't knowing or being taught or learning the algorithm, or finding it difficult; it's making sure you find and deal with every corner case, first time, without testing. For example: is an empty array handled properly? An array with duplicates? Is every item, including first and last, found correctly? What about arrays with an even number of elements vs odd, vs power of two? How about an array with over 1 billion elements (the integer overflow problem)? Are values before and after the sorted range indicated properly? If working with duplicates, do you want a found index at the start of the range, or at the end?
I would rather think in invariants - knowing what must be true at particular points in the code, at the start of loop bodies, etc. Essentially, doing a proof in one's head.
