Algorithm to chase a moving target
First of all, I will assume that by


  Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$


you actually mean


  Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S + k \mod n$, where $k$ is selected uniformly at random from $$\left\{- \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|, \ldots, -1, 0, 1, 2, \ldots, \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|\right\} $$


Otherwise, it is not entirely clear that $f_S \in \{ 0, ..., n-1\}$ always holds and how exactly $f_S \pm k$ behaves.

Using this, the problem basically comes down to "missing as much as possible". Observe that the closer we shoot the rabbit, the larger hops he makes; in the extreme case we have $f_S - x = \pm 1 \mod n$. This results in a uniform hop between $ -(\lfloor n/2 \rfloor \pm 1)$ and $ (\lfloor n/2 \rfloor \pm 1)$, which basically completely randomizes the position of the rabbit again. On the other hand, if we miss as badly as possible - by an offset of $f_S - x \mod n = \lfloor n/2 \rfloor$, the rabbit actually does not move at all (!) and the black box actually updates us on this fact. Therefore, we can just turn around and shoot the rabbit.

We are left with finding a procedure for missing increasingly in each shot. I propose a simple "binary search". (I will conveniently omit the rounding.) It proceeds roughly as follows:


Reset and shoot at an arbitrary position until you get from the blackbox the answer $(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$ This takes a constant amount of steps in expectation.
Now, we know that the rabbit's past position $f_S$, and that it did not move more than $\frac{1}{4}n$ steps in either direction. This basically halves our search space in the next iteration, since the rabbit has to be at a position $f_S' \in \{ (f_S - \frac{1}{4}n) \mod n, ..., f_S, ..., (f_S + \frac{1}{4}n) \mod n \}$
Recurse: Shoot at position $f_S - n/2 \mod n$. With probability $1/2$, the position $f_S'$ the rabbit jumped onto in step 1&amp;2  lies the range $\{ f_S - \frac{1}{8}n, ..., f_S, ..., f_S + \frac{1}{8}n \}$. In that case we halved the search space once more. With probability $1/2$, the rabbit did not jump in that range, but since we know that $f_S' - x \mod n = f_S' - f_S + n/2 \mod n \in \{ \frac{1}{2}n - \frac{1}{4}n, ..., \frac{1}{2}n + \frac{1}{4}n \}$, we have the same assumptions as in step (2) and therefore lose nothing.


Each step needs $2 = \mathcal{O}(1)$ expected time to succeed and halves the search space, yielding an overall of $\mathcal{O}(\log n)$ expected number of steps.