I also stumbled upon this question few weeks ago. Of course one can always try all convergents since there are not that many (the denominators grow exponentially fast), but we know already that exactly one of them equals $s/r$ (if phase estimation ran successfully). Of course it can happen that $s$ has a common factor with $r$ but how to deal with this is discussed in the book - so we do not care here. So it is an interesting question to ask which one it is.
In fact, it really is the last convergent with a denominator smaller than $N$.
I gave a proof here. But I will repeat it in this answer.
Let us recall that we not only know that $r<N$ we also know that $\varphi$ is approximated up to $2L+1$ bits (with probability at least $1-\varepsilon$) according to the book (not just $L$ bits). This shows:
$$
\left|\frac{s}{r} - \varphi\right| \leq \frac{1}{2N^2},
$$
since $N$ is an $L$ bit number. Note that this information is lost in Theorem 5.1 of the book. The claim now directly follows from this little Lemma:
Let $s < r < N$ be non-negative integers and $\varphi\in[0,1)$ real. Assume
$$
\left|\varphi - \frac{s}{r}\right| < \frac{1}{2 N^2} .
$$
Then $s/r$ is a convergent of $\varphi$ and the next convergent has a denominator which is
larger than $N$.
PROOF: The book already showed that $s/r$ is a convergent of $\varphi$. Let us focus on the claim that it is the last one. Let us write $s/r=p_n/q_n$ with coprime nominator and denominator. Furthermore assume that $\varphi=[a_0,\ldots,a_n,z_{n+1}]$ where $z_{n+1}$ is allowed to be /real/ number (and at least $1$).
It can be shown (see e.g. here), that
$$
\varphi - \frac{p_n}{q_n} = \frac{(-1)^{n+1}}{q_n(z_{n+1}q_n+q_{n-1})} .
$$
In fact this follows from the better known formula (see e.g. wikipedia):
$$
\varphi = \frac{z_{n+1}p_n + p_{n-1}}{z_{n+1}q_n + q_{n-1}} .
$$
Also recall the well known recursion formulas:
$$\begin{align*}
p_{n+1} &= a_{n+1}p_n + p_{n-1} , \\
q_{n+1} &= a_{n+1}q_n + q_{n-1} , \\
z_{n+1} &= (z_n - \lfloor z_n \rfloor)^{-1}
\end{align*}$$
Hence:
$$
q_n (q_{n+1} + q_n/z_{n+2}) = q_n (z_{n+1} q_n + q_{n-1}) \geq 2 N^2 .
$$
Since $q_n < N$, $q_n < q_{n+1}$, and $z_i\geq 1$ we deduce $q_{n+1}>N$. QED.
This should answer the question. But let me give some final note on fraction.limit_denominator(N)
. In general this does not return a convergent. Instead it returns a so called best approximation (see the python documentation), that is, a fraction so that no other fraction with smaller denominator better approximates the target. Convergents are best approximations but not the other way around (For example $1/2$ is a best approximation of $5/7$ but no convergent).
But this does not imply that one cannot use fraction.limit_denominator(N)
to find $s/r$. A lemma like the above but with convergents replaced by best approximations might be true. I didn't look into that. But I also suspect that to efficiently compute best approximations one has to first
calculate convergents anyway.