# Checking for rational numbers with small denominators in an interval

I have been given two rational numbers $$\frac{a}{b}$$ and $$\frac{c}{d}$$, and I have been told that there is a unique rational number $$\frac{p}{q}$$ satisfying $$|q| \leq n$$ (where $$n$$ is some known natural number) which lies in the interval $$[\frac{a}{b}, \frac{c}{d}]$$.

How do I find this $$\frac{p}{q}$$? The rational numbers in the input are given as ratio of integers. We can assume that operations on integers take constant time.

The best strategy I know is something that takes time proportional to $$n$$. It tries to find if there is a rational number with denominator $$i$$ where $$i$$ ranges from $$1$$ to $$n$$. It goes something like this:

1. Check if there is any integer between $$\frac{a}{b}$$ and $$\frac{c}{d}$$. To do this, check first if $$\frac{a}{b}$$ or $$\frac{c}{d}$$ is an integer itself. If not, compute $$\lfloor > \frac{a}{b} \rfloor$$, and check if $$\lfloor \frac{a}{b} \rfloor + 1$$ is smaller than $$\frac{c}{d}$$.
2. Multiply both $$\frac{a}{b}$$ and $$\frac{c}{d}$$ with 2. Check if there is an integer between these two numbers using the steps in 1, and renormalize this obtained rational number by dividing with $$2$$.
3. Multiply both of them with $$3$$ ...
4. ...

What are some other ways of doing this?