What is the complexity of a bracketed search using mediants?
The relation between the Stern–Brocot tree and Farey sequences shows that if $0 &lt; p/q &lt; 1$ and $(p,q) = 1$ (i.e., $p/q$ is a reduced fraction) then $p/q$ is at the $q$th level of the tree. Since the running term of your algorithm is linear at the level in which you terminate, your algorithm takes time $O(q)$, where $p/q$ is the answer; but this is not so helpful.

You haven't specified what your stopping criterion is, but presumably you have some error threshold $\epsilon$. The question therefore is for which Farey sequence is it the case that adjacent terms are at distance at most $2\epsilon$ (and so every point is at distance $\epsilon$ from some point). Using the fact that the distance between adjacent fractions $p_1/q_1,p_2/q_2$ in a Farey sequence is $1/(q_1q_2)$, it is not hard to show that the maximal distance at the $q$th Farey sequence is $1/q$. Therefore if you are aiming at a distance of $\epsilon$, then your algorithm will run in time $O(1/\epsilon)$ in the worst case.

However, "most" adjacent fractions at the $q$th Farey sequence are at distance $O(1/q^2)$, and so on average you would probably expect a running time of $O(\sqrt{1/\epsilon})$ (unfortunately, this average is with respect to the input rather than the algorithm).