Rational with minimal denominator between two rationals My question from an easy problem.

$p,q$ are positive integers such that $$
\frac{5}{9}<\frac{p}{q}<\frac{4}{7}
$$ find $p,q$ such that $q$ is the smallest number that satisfies this inequality.

Draw the line of $ y<\frac{9}{5}x$ and $y>\frac{7}{4}x$ , we can "observe" that $\frac{9}{16}$ is such number.
However, if the question becomes

$a,b,c,d$ are positive integers such that $$\frac{a}{c}<\frac{b}{d}
$$ find $p$,$q$ such that $q$ is the smallest number that satisfies the inequality

$$\frac{a}{c}<\frac{p}{q}<\frac{b}{d}$$ 
No idea about this.

What do we get with continued fractions?
$\dfrac{5}{9}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{4}}}$
$\dfrac{4}{7}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3}}}$
The fractions are identical until we get to the last layer where one has a $4$ and the other has a $3$.  Were there an integer between $3$ and $4$ we could replace the last layer with the smallest such integer, following the accepted answer here.
We don't have such an integer between $3$ and $4$ so this does not appear to work.  But we can force the issue by rendering
$4=3+\dfrac{1}{1}$
$3=3+\dfrac{1}{M}$
where $M$ is taken as approaching infinity.  Then we have
$\dfrac{5}{9}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{1}}}}$
$\dfrac{4}{7}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{M}}}}$
Now we put $2$ as the smallest integer between $1$ and $M$ to get an intervening fraction with a minimal denominator.  Thus
$\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{2}}}}=\dfrac{9}{16}$
