Guess the number with one-call delayed feedback

A hidden integer secret lies in [1, n], inclusive. You can't read it. The only way to learn about it is a comparison service with one method:

check(guess: int) -> str

The service answers one call late. Each call submits a new guess, but the string it returns is about the guess you submitted on the previous call:

• The very first call returns "PENDING" (there is no earlier guess yet).
• After that, each call returns "TOO_LOW", "TOO_HIGH" or "CORRECT", comparing the previous guess with secret.

Implement find_secret(n, server) -> int. It returns the secret.

Requirements

• It must always return the right value. You may return as soon as the secret is known by elimination; you don't need to see "CORRECT".
• Keep the number of check calls low in the worst case. Plain binary search that waits out every delay takes about 2 * log2(n) calls. Aim to do clearly better.
• 1 <= n <= 10^9. Guesses may be any integer, but guesses outside the remaining range waste a call.

Example 1 (n = 2, secret = 2)

Return 2 after 2 calls.

Example 2 (n = 10, secret = 7)

Call check(5) and get PENDING. Before the verdict on 5 comes back, bet that the secret is above 5 and call check(7). It returns TOO_LOW for 5, so the range is now [6, 10] and the bet was useful. Call check(8): it returns CORRECT for 7. Return 7 after 3 calls.

Be ready to explain how many calls your strategy needs in the worst case, and why.