$\DeclareMathOperator*{\argmax}{arg\,max}$ I am interested in finding an efficient algorithm for the following problem:

Let $x \in [0,1]^n$ be some vector, with $x_n = 1$. We want to recover $x$, solely by asking queries of the form $$\texttt{argmax}(x+v) := \argmax_{1 \le i \le n}{x_i + v_i}$$ where $v \in \mathbb{R}^n$ is an arbitrary additive shift. In case of multiple occurrences of the maximum value, the smallest $i$ is returned.

A simple algorithm is to do binary search over each component of $x$ one-by-one. This requires $O(n \log 1/\epsilon)$ queries to recover $x$ up to precision $\epsilon$.

Is it possible to do better? My intuition is that it might be, as every query $i \gets \texttt{argmax}(x + v)$ gives us $\log_2 n$ bits of information. So in principle we could hope for an algorithm that uses $O(\frac{n \log 1/\epsilon}{\log_2 n})$ queries.