it's better to measure it more directly.
Firstly, how can we do that ? There's no way we can grant each candidate an evaluation period that lasts two or three monhts -- which is what it'd take to measure his performance directly. So, we need some heuristics.
Secondly, "is the candidate CS-literate at all" is just the kind of heuristic that we can use for this. And, IMO knowing about binary search (not necessarily by name, especially if the candidate is not a native English speaker) is a great test for this heuristic. It's pretty much the CS equivalent of "can you form words into sentences".
One measure is to get them to do a small project (a few hours worth as most) of a similar (but simpler) nature to what your company does. That may not be perfect but it's a lot closer than whiteboard algorithms. IIRC research suggests that of all forms of job candidate evaluation, "work samples" such as this have the highest correlation with subsequent performance.
This is the sixth bimonthly 'What are you working On?' thread. Previous threads are here. So here's the question:
What are you working on?
Here are some guidelines: