Reason About Binary Search with One-Call-Delayed Feedback

Problem Statement

In standard binary search, each query immediately reveals whether the guess was too low, too high, or correct. In distributed or pipelined systems, feedback is often delayed.

You are searching for a hidden integer target in the inclusive range [1, n]. You interact with an oracle through an interface oracle.guess(x: int) -> int | None with the following delayed-feedback specification:

1. First Call: oracle.guess(x) registers x as guess #1 and returns None (no previous guess exists).
2. Call k (k >= 2): oracle.guess(x) registers x as guess #k and returns the comparison result for guess #(k - 1):
   • -1 if guess #(k - 1) target
3. Flush / Termination: If you receive 0, the previous guess was the target, and you can return it immediately. If your search narrows down to a single candidate or you need to inspect the result of your last issued guess, you may make an arbitrary valid dummy guess (e.g., within [1, n]) to flush the pending result.

Implement the function find_target(n: int, oracle: DelayedOracle) -> int to find target using O(log n) total calls to oracle.guess.

Function Signature

class DelayedOracle:
    def guess(self, x: int) -> int | None:
        ...

def find_target(n: int, oracle: DelayedOracle) -> int:
    pass

Constraints

• 1 <= target <= n <= 10^9
• The total number of calls to oracle.guess must be strictly bounded by C * log2(n) + O(1) for a small constant C (e.g., ` None # Guess 4 registered

1. oracle.guess(2) -> 1 # Feedback for 4: 4 > 3 (+1). Target in [1, 3].
2. oracle.guess(1) -> -1 # Feedback for 2: 2 -1 # Feedback for 1: 1 0 # Feedback for 3: 3 == 3 (0). Found!

Output: 3

### Example 2
```text
Input: n = 1, target = 1

Execution trace:
1. oracle.guess(1) -> None  # Guess 1 registered
2. oracle.guess(1) -> 0     # Feedback for 1: 1 == 1 (0). Found!

Output: 1

Notes & Edge Cases

• When n = 1, a startup guess followed by a flush guess is required to read the feedback.
• Handle state correctly when an earlier guess turns out to be the target while another guess was already in flight.
• Your search interval invariant must account for the fact that at any step k, the feedback received corresponds to guess k - 1, not the most recently submitted guess.