  We introduce a search problem generalizing the typical setting of Binary
Search on the line. Similar to the setting for Binary Search, a target is
chosen adversarially on the line, and in response to a query, the algorithm
learns whether the query was correct, too high, or too low. Different from the
Binary Search setting, the cost of a query is a monotone non-decreasing
function of the distance between the query and the correct answer; different
functions can be used for queries that are too high vs. those that are too low.
The algorithm's goal is to identify an adversarially chosen target with minimum
total cost. Note that the algorithm does not even know the cost it incurred
until the end, when the target is revealed. This abstraction captures many
natural settings in which a principal experiments by setting a quantity (such
as an item price, bandwidth, tax rate, medicine dosage, etc.) where the cost or
regret increases the further the chosen setting is from the optimal one.
  First, we show that for arbitrary symmetric cost functions (i.e.,
overshooting vs. undershooting by the same amount leads to the same cost), the
standard Binary Search algorithm is a 4-approximation.
  We then show that when the cost functions are bounded-degree polynomials of
the distance, the problem can be solved optimally using Dynamic Programming;
this relies on a careful encoding of the combined cost of past queries (which,
recall, will only be revealed in the future). We then generalize the setting to
finding a node on a tree; here, the response to a query is the direction on the
tree in which the target is located, and the cost is increasing in the distance
on the tree from the query to the target. Using the k-cut search tree framework
of Berendsohn and Kozma and the ideas we developed for the case of the line, we
give a PTAS when the cost function is a bounded-degree polynomial.
