I don't think this is an especially great question, but I worked at one company that asked this question and most people who got it right did not seem to have a

I don't think this is an especially great question, but I worked at one company that asked this question and most people who got it right did not seem to have an implementation memorized. I say this because they got it right only after writing a buggy version and fixing some bugs. Another company was in the habit of asking a different question that gets to the heart of the matter of "Can you think with invariants?" but is not nearly as tricky as binary search. That seemed better to me.