As @DonAntonio pointed out, for an arbitrary choice of $a,r$ there may not be a solution. And even if there is a solution, it is not necessarily true that there's an $m$ with $a^{2m}\equiv 1$ and $a^{m}\equiv p-1$ as you suggested in your comment. For example consider $2^3\equiv 1 \pmod{7}$.
So let us assume that $a$ is a primitive root modulo $p$ so in fact there is an index $n$ for every $1\le r
In a literal sense it is possible to know which half $n$ is in without necessarily finding it. You can compute $a^i \bmod p$ for $i=1,2,\ldots$ and stop if you find $r$ or if you get to $i=(p-1)/2$. But I suspect you were looking for something more efficient.
It is unlikely that a much more efficient method is known, since having one would allow computation of discrete logarithms quickly.
If given $r$ you can find that $n$ is in the "first half", then choose a $t_1$ close to $p/4$ and solve for $n_1$ such that $a^{n_1}\equiv ra^{t_1}\pmod{p}$. This let's you determine whether $n$ is in the first or second quarter (more or less). If $n$ was in the "second half" solve $a^{n_1}\equiv ra^{-t_1}$ for $n_1$ to place $n$ in the third or fourth quarter.
Similarly, pick $t_2$ close to $p/8$ and solve $a^{n_2}\equiv ra^{\pm t_1\pm t_2}$ with signs as necessary to place $n$ in an eighth of the range. You can use a binary search this way to solve for the exact value of $n$ in $O(\log p)$ steps.