algorithms - Finding unknown integer-valued polynomials using inequalities

I've come across this interesting inequalities problem recently, which seemed straight-forward at first glance but has proven interesting enough to ask about it here.

Suppose you are given the degree of an unknown polynomial, and are told that all the coefficients are integers and are all within $min le a_k le max$. Also, you have access to an oracle who will evaluate p(q), the unknown polynomial, and compare it to your guess $g_q$, where q is the number of previous guesses you have made, and determine if your guess was less, greater than, or exactly equal to the unknown polynomial.

What is the optimal method of choosing guesses, given previous results, in order to make a correct guess as soon as possible in the worst case?

If the degree is d and the coefficients are bounded by [min, max] then it would seem the best possible method would require slightly less than $ frac {d log (max - min + 1)}{log 2}$ by binary search. Its slightly less because with an answer of > from the oracle, you exclude both the values less than and those equal to the guess, which could be more than 50% of possibilities.

If the median of the evaluated values at q of all of the remaining possible polynomials can be found, than guessing that value would be guaranteed to eliminate at least half of the possibilities. But is there any efficient way to find the median of a function of a set of polynomials that are only identified by inequalities?

For the first guess, q is zero and therefore all but the constant term of the polynomial are irrelevant. It makes sense then to make g(0) to be $frac {min + max}{2}$. But after that, the best way of finding the median quickly seems elusive.

As an example, make min = -100, max = 100 and d = 1. $frac {-100 + 100}{2}$ = 0, so g(0) should be 0. If the oracle returns > then we know $0 < a_0 le 100$ or $1 le a_0 le 100$ since we are dealing with integer coefficients.

An ideal method would include an efficient way to find the median and characterize the set of possibilities given the previous answers from the oracle. But medians can be hard to calculate so an efficient method to calculate the mean of p(q) for the set of possibilities would be close enough if an efficient method doesn't exist for medians.