Like skysurf I could not find any ancient record for binary search, so this is more of an extended comment. The problem may be that before computer science algorithms were either practical, or games for mathematically inclined, and the binary search wasn't attractive either practically or recreationally. Of course, if we cast the net wider something ancient can be found. Already Plato and Aristotle constructed classifications based on binary dichotomies, which were later depicted as binary Porphyrian trees, and reincarnated in computer science as sorted binary trees, that are custom made for binary searches.
A closer relative concerns continuous cousin of binary search, the method of bisection. It appears that it was used by Bolzano in 1817 to prove the intermediate value property (but see Mikhail's comment below on Stevin's prior use), and the numerical method based on it was developed shortly thereafter. To find a zero of a continuous function on an interval where it takes values of opposite signs at the ends one bisects the interval, takes the subinterval with opposite signs, bisects again, etc. Unlike binary search bisection may never halt, but it converges to a zero, and produces approximations with obvious error bounds at each step.
Unfortunately, I could not find an early reference for a yes/no number guessing game, although "think of a number" tricks with extra information occur as early as the Rhind papyrus (c. 1800 BC). When extra information is provided on how badly a guess fails, even in a simple form like cold/warmer/hot, it is also inefficient since it doesn't take it into account. The same goes for bisection, if we take into account end values rather than just signs double false position converges much faster for practically relevant functions. And it is indeed ancient, occurring already in Chinese Nine Chapters from before 220 AD.