In this task we are going to see two simple applications of binary search related to square root computations.

The first problem that we are going to solve is the following:

Given a positive integer \(n\) find the largest integer \(x\) such that \(x^2 \leq n\). This value is called the integer square root of \(n\).

We will solve this problem using binary search. Note all that we are doing here can be done using the sqrt function present in most languages. But using it would be pointless since the one of the goals of this tasks is precisely to teach you how to write an algorithm for computing square roots.

We are going to reason in the same way as we did to find an element in a sorted array.

Suppose that we pick some value \(m\) and compare \(m^2\) to \(n\). What can we deduce?

Since the function \(x \mapsto x^2\) in non-decresing, we have the same kind of properties that we had with our sorted array:

• if \(m^2 < n\) then we can dismiss all values \(x < m\)
• if \(m^2 > n\) then we can dismiss all values \(x > m\)

In the same was as before, we will keep track of the current interval that we are considering. You can select that interval by selecting \(L\) and \(R\) so that the answer is in the interval \([L, R[\). In this case we can choose \(L = 0\) and \(R = n + 1\).

We can then write the following code:

static int integerSqrt(int n) {
    long L = 0;
    long R = n + 1;
    while(R - L >= 2) {
        long M = (L + R) / 2;
        if(M * M <= n) L = M; // dismiss all values < M
        else R = M; // dismiss all values > M
    }
    return (int)L;
}

In the code, we use long variables because the multiplication M * M can overflow otherwise. The cast to \(int\) in the end is safe since we know that the answer is at most \(n\).

This code runs in \(O(\log(n))\) for the same reason as before.

That is it for integer square roots. How about real square root?

Given a positive real number \(n\) find a real number \(x\) such that \(x^2 = n\).

Performing binary search on a continuous range is similar. The biggest change lies in the stopping condition. Since the search interval is not discrete anymore, it will never become empty. Thus we will stop when it becomes small enough. In this example we will stop once \(|L - R| \leq 10^{-6}\). You can change the power if you want more of less precision.

static double sqrt(double n) {
    double L = 0;
    double R = n;
    while(Math.abs(L - R) > 1e-6) { // check whether the interval is small enough
        double M = (L + R) / 2;
        if(M * M <= n) L = M;
        else R = M;
    }
    return L;
}

Another (probably better) criteria that people often use for continuous binary search is to simply run the code for a fixed number of iterations. At each iteration the size of the interval is halved so after \(k\) iterations its size is \(n / 2^k\). Therefore, for any reasonable input, if we run for, say \(k = 80\), iterations, the size of the interval will be sufficiently small to be close the the actual answer.

The following code shows this.

static double sqrt(double n) {
    double L = 0;
    double R = n;
    for(int i = 0; i < 80; i++) {
        double M = (L + R) / 2.0;
        if(M * M <= n) L = M;
        else R = M;
    }
    return L;
}

Note: We are do not recomment you, in any way, to compute square roots using this algorithm. You should use the built-in function of your language. The goal was just to illustrate how you would do a binary search on a continuous interval.