Find a Hidden Number When Each Comparison Answer Arrives One Call Late

A hidden integer `x` lies in the range `1` to `n`. You can learn about it only through an API call `check(g)`, which compares a guess `g` with `x`. The twist is that the API's answer is **delayed by one call**: each call to `check(g)` submits the guess `g`, but returns the comparison result for the guess submitted in the *previous* call. The very first call returns nothing (`None`). A result says whether that earlier guess was too low (`-1`), correct (`0`) or too high (`1`). Write a function `find_hidden(n, check)` that returns `x`, using as few calls to `check` as possible in the worst case. Start with a correct version, then improve the worst-case number of calls, and explain how many calls your approach needs as a function of `n`. The exact API contract was not reported; the one above is the working assumption for this exercise. ```hint Correct first Before optimizing, consider the simplest way to run an ordinary binary search on top of an API that always answers one call late, and count its calls. ``` ```hint Make the waiting call useful The call that fetches the previous answer must itself submit some guess; think about where to place that guess so it helps regardless of which answer arrives. ``` ### Clarifying Questions - Is the delay always exactly one call, or can answers arrive at unpredictable later times? - Is `n` known in advance? - Is the goal to minimize the worst-case number of calls, or the average? - Must the function end by having `check` confirm `x` with a result of `0`, or is deducing `x` enough? - Is there a limit on the total number of calls? ### What a Strong Answer Covers - A correct baseline that adapts binary search to the one-call delay, with its call count - An improved strategy that uses every call productively, and its worst-case call count as a function of `n` - A clear argument for why the improvement works, and whether it is optimal - Careful handling of edge cases: `n = 1`, tiny ranges, the first `None` and early termination on a correct guess - Tests that simulate the delayed API and check every possible hidden value ### Follow-up Questions - The delay is now `d` calls instead of one. How does your strategy generalize? - Several guesses may be submitted in one call and answered together one call later. How does that change the search? - Answers can now be wrong with a small probability. How would you still find `x` reliably? - The answers can arrive out of order, each tagged with its guess. What changes?