Approximation with imperfect dichotomy oracle
I found thanks to @YuvalFilmus 's advice! (if you want me to remove this answer and post it yourself, feel free to ask)
1. We find a factor 4 approximation
If we know a value r s.t. O(r/2) = True and O(r) = False, then we know that x is in [r/2, 2*r[.
And for any starting point y, while O(y) = True we multiply y by 2 until we have O(y) = False, and conversely for O(y) = False to find such a value.
By the properties of the oracle, this terminates. We have a logarithmic complexity. But when evaluating $O(y \times 2^k)$ for an integer k, we know that there is an index that separates the True values from the False. Thus we can apply binary search on this logarithmic scale to have a $\log(\log(x))$ number of evaluations of the oracle.
2. We transform a $2^{1+\frac{1}{k}}$ approximation in a $2^{1+\frac{1}{2k}}$ approximation
Suppose you know $x\in[a, b[$ with $\frac{b}{a} = 2^{1+\frac{1}{k}}$.
Take $c = a * 2^\frac{1}{2k}$.
We know that if $x \in [a, c[$, then $O(c)$ is false, and that if $x \in [2c, b[$, then $O(c)$ is true.
Thus we can eliminate one interval of ratio $2^\frac{1}{2k}$, and the remaining interval is of ratio $2^{1+\frac{1}{k}-\frac{1}{2k}}$ = $2^{1+\frac{1}{2k}}$.
3. Complexity
We make $\log(\log(x))$ calls to the oracle in the first stage, and then $i$ to get a $2^{1+\frac{1}{2^i}}$ approximation factor.
For example, if you work with integers, the stop condition is $ x * (2^{1 + \frac{1}{2^i}} - 2) &lt; 1 $. A Taylor expansion gives us $i &gt; \log(x) + 1$ with the first term, so $i &gt; \log(x) + 2$ should be fine.
4. Other strategies
Like shown below, more evaluations per step could get us immediately better approximation factors than 2.
However, it requires too much evaluations, with no improvement in the worst case when the oracle is a threshold function.
Let $x_1, x_2 = \frac{r}{2}, x_3, x_4=b, x_5, x_6=2r$ be numbers in geometric progression of ratio $\sqrt2$ with $r$ found after the first stage.
We know $O(x_2) = T, O(x_4) = F, O(x_6) = F$, and we know $x \in [x_2, x_6[$. We split this interval in 4 and look at the values of $O(x_1), O(x_3), O(x_5)$. We note $?$ when a value can be True or False.
For $x\in[x_2,x_3[$, the possible values are $?, F, F$.
For $x\in[x_3,x_4[$, the possible values are $T, ?, F$.
For $x\in[x_4,x_5[$, the possible values are $T, ?, F$.
For $x\in[x_5,x_6[$, the possible values are $T, T, ?$.
If we get $O(x_1) = F$ or $O(x_5) = T$, we know a $\sqrt2$ factor approximation of x. Else, the value of $x_3 = c$ allows us to eliminate either the leftmost or the rightmost interval, which is exactly the first step of the second stage of our general strategy to transform a $4 = 2^{1 + \frac{1}{1}}$ approximation into a $2\sqrt2 = 2^{1 + \frac{1}{2}}$ approximation.