Did you understand the algorithm correctly? It is indeed logarithmic in n+m.
E.g.

>>> find(34, 53)
find(x=34, y=53, a=0, b=1, c=1, d=0)
find(x=34, y=53, a=0, b=1, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=2, d=3)
find(x=34, y=53, a=3, b=5, c=2, d=3)
find(x=34, y=53, a=5, b=8, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=9, d=14)
find(x=34, y=53, a=16, b=25, c=9, d=14)
find(x=34, y=53, a=25, b=39, c=9, d=14)
'LRLRRRLRR'

Or why do you think think that it is quadratic?

Hi all, Aeren is right that the algorithm is quadratic. First of all, proper search on the Stern-Brocot tree should compress the output in run-length encoding. So, if L or R is repeated $k$ times, the number $k$ should be found with binary search (or with floor function, if it's possible based on the target function), and the output should effectively be the continued fraction of $\frac{x}{y}$. Otherwise, the size of the output might reach $x+y$, e.g. when $x=1$ or $y=1$.

Another thing to note is that it returns strings like 'L' + find(...), which means that it copies the result every time before appending L or R to its beginning (so, it's in fact quadratic). Overall, we should fix the algorithm to better correspond to what is explained here.

Did you understand the algorithm correctly? It is indeed logarithmic in n+m. E.g.

>>> find(34, 53)
find(x=34, y=53, a=0, b=1, c=1, d=0)
find(x=34, y=53, a=0, b=1, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=2, d=3)
find(x=34, y=53, a=3, b=5, c=2, d=3)
find(x=34, y=53, a=5, b=8, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=9, d=14)
find(x=34, y=53, a=16, b=25, c=9, d=14)
find(x=34, y=53, a=25, b=39, c=9, d=14)
'LRLRRRLRR'

Or why do you think think that it is quadratic?

It takes N calls to reach 1/N (1/1 -> 1/2 -> 1/3 -> 1/4 -> ... -> 1/N)

@Aeren1564 My bad. I was completely wrong here.
I remember using a faster version in a contest once, and I was pretty sure that I copied it from here. But I guess I was mistaken.

We should fix that, and provide a faster version. Implementing it with binary search doesn't look too hard.

b19ce68: I rewrote the recursive code into iterative manner, so that it's $O(p+q)$ rather than $O((p+q)^2)$ now. I also added $O(\log(p+q))$ code that finds the compressed description of the path from root for a specific fraction $\frac{p}{q}$, and some comments on how one should use binary search to find coefficients in a more generic case. Keeping this open, as we still might need generic search function with predicates, but at least it shouldn't be considered a bug anymore.