Complexity of approximating a real function using queries Consider the following computational problem, where $I$ is the real interval $[-1,1]$:

There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of the kind: &quot;Given $x\in I$, what is $f(x)$?&quot;. Let $x_0$ be an element of $I$ such that $f(x_0)=0$ (if it exists). Your goal is to find a value $x$ such that $|x-x_0|&lt;\epsilon$. How many queries do you need, as a function of $\epsilon$?

All real numbers have infinite precision, as in the Real RAM model. It is allowed to do arbitrary computaitons on such real numbers - the only costly operations are the queries.
Here, the solution is simple: using binary search, the interval in which $x$ can lie shrinks by 2 after each query, so $\log_2(1/\epsilon)$ queries are sufficient. This is also an upper bound, since an adversary can always answer in such a way that the possible interval for $x$ shrinks by at most 2 after each query.
However, one can think of more complicated problems of this kind, with several different functions and possibly different kinds of queries.
What is a term, and some references, for this kind of computational problems?
Related posts in other sites:

First posted on cs.stackexchange.
This MathOverflow post is related, but there it is required to use a finite number of registers with a finite precision.
Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the minimal number of evaluation queries needed to uniquely identify $f$? As already noted in the OP, the question only makes sense if one fixes a function class $F$ of possible candidate functions $f$ to consider.
This is a well-studied problem, where the key notion is the teaching dimension (which is the minimum size of a teaching set), see here:
https://www.cs.umd.edu/sites/default/files/scholarly_papers/NealGupta.pdf
A teaching set $S\subset X$ is such that the values of $f$ on $S$ uniquely identify $f\in F$, for a given fixed function class $F$.
Nothing is stopping you from defining an $\epsilon$-teaching dimension for real-valued functions. You can define an $\epsilon$-teaching set $S\subset X$ to be such that all $f\in F$ that agree on $S$ all lie within an $\epsilon$-tube (i.e., are all within $\epsilon$ in $\ell_\infty$ distance).
As you can see from the discussion in that paper I linked, the teaching dimension is a rather stringent notion, which motivates more &quot;interesting&quot; variants, such as the recursive teaching dimension. Here again, I encourage you to explore its natural real-valued extensions.