I have a function $f: [0,1]\rightarrow[0,1], x \mapsto f(x)$, for which I don't have an explicit expression. For each evaluation I need to find the maximum value $\alpha \in [0,1]$ for which some condition $C$ is true. Evaluating this condition is quite computationaly expensive. I currently use a bisection method for finding $f(x)=\alpha^\ast$. I do know, however, that $f(0)=0$, $f(1)=1$ and $f$ is strictly increasing. Furthermore, I know that the function has a sort of hockey stick curve, where it increases very slowly at the beginning, to then rapidly increase to $1$ at the end of the domain.
I need evaluations of $f$ for around a $100$ values of $x$ equaly spaced in the domain $[0,1]$. Currently I do this by performing the bisection a hundred times with starting interval $[0,1]$. This is quite inefficient, especially because the result is almost constant in the beginning.
To speed this up, I tried reusing the final interval $[a,b]$ from the previous bisection in the next one. Then I start by checking if $C(a)$ is true and $C(b)$ is false and if so, I start the bisection with this smaller interval $[a,b]$. If not, I start with the interval $[0,1]$. This sped things up quite well for the low values of $x$, where the subsequent evaluations are often in the same interval, but when $f(x)$ starts increasing faster, the small interval is unusable the majority of the time and I have to restart from $[0,1]$.
I there some way of improving this any further, or is there perhaps an alternative to the bisection method I can look into?
Say the values you want to find are $f(x_1) \le f(x_2) \le \dots \le f(x_{100})$. One possible improvement you could make is beginning with the bisection algorithm to compute $f(x_{50})$. Then, your remaining bisection searches can be done on the interval $[0, f(x_{50})]$ for computing $f(x_1), \dots, f(x_{49})$, and on the interval $[f(x_{50}), 1]$ for computing $f(x_{51}), \dots, f(x_{100})$.
This cuts down your interval sizes by at least a factor of $2$ for half the remaining searches that you need to do, potentially much more. (For example, if $f(x_{50})$ is pretty small, then you've learned that $f(x_1), \dots, f(x_{49})$ are also fairly small, putting them in much shorter intervals.)
Then, repeat this strategy on the first half of the problem (computing $f(x_{25})$ first) and on the second half of the problem (computing $f(x_{75})$ first).