  We study a generalized binary search problem on the line and general trees.
On the line (e.g., a sorted array), binary search finds a target node in
$O(\log n)$ queries in the worst case, where $n$ is the number of nodes. In
situations with limited budget or time, we might only be able to perform a few
queries, possibly sub-logarithmic many. In this case, it is impossible to
guarantee that the target will be found regardless of its position. Our main
result is the construction of a randomized strategy that maximizes the minimum
(over the target position) probability of finding the target. Such a strategy
provides a natural solution where there is no apriori (stochastic) information
of the target's position. As with regular binary search, we can find and run
the strategy in $O(\log n)$ time (and using only $O(\log n)$ random bits). Our
construction is obtained by reinterpreting the problem as a two-player
(\textit{seeker} and \textit{hider}) zero-sum game and exploiting an underlying
number theoretical structure.
  Furthermore, we generalize the setting to study a search game on trees. In
this case, a query returns the edge's endpoint closest to the target. Again,
when the number of queries is bounded by some given $k$, we quantify a
\emph{the-less-queries-the-better} approach by defining a seeker's profit $p$
depending on the number of queries needed to locate the hider. For the linear
programming formulation of the corresponding zero-sum game, we show that
computing the best response for the hider (i.e., the separation problem of the
underlying dual LP) can be done in time $O(n^2 2^{2k})$, where $n$ is the size
of the tree. This result allows to compute a Nash equilibrium in polynomial
time whenever $k=O(\log n)$. In contrast, computing the best response for the
hider is NP-hard.
