Compute square root using (bit) additions and shifts as primitives
An iterative algorithm seems like it should work.

Let $M=\lfloor N/4 \rfloor$.  Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously).

Now we want to find $y=\lceil \sqrt{N} \rceil$.  What are the possible values of $y$?  I'm pretty sure the only possible values are $y=2x$ or $y=2x+1$.   And, it's easy to try both of them and see which is correct.  In particular, for $y=2x$, we have $y^2=4x^2$, which can be obtained from $x^2$ by two left-shifts ($O(1)$ time); for $y=2x+1$, we have $y^2=4x^2+4x+1$, which can be obtained from $x^2$ and $x$ with four left-shifts and two additions ($O(1)$ time).  Now just compare those two values to $N$ to see which one is correct.

In this way, we get an iterative algorithm where we do $n/2$ iterations, and where each iteration takes $O(1)$ time.  The total running time is $O(n)$, as required.

I realize this didn't use binary search.  Oh well.