This is a game with imperfect information, and the optimal strategy for each player is probably different from "pick any number at random" and "run off-the shelf binary search".
Perfect information = Chess Imperfect information = Poker
This fits into the latter category - if player 2 knew everything that player 1 knows, they would behave differently.