Program to Find Square Root of an Integer Using Binary Search

by

This article will discuss how to find the square root of an integer efficiently using Binary Search. If the number is a perfect square, the program should return the square root, else return the floor of the square root of the number. Before that we first discuss the naive approach to find the square root of the number. The given code is implemented in C++ but the same logic can be implemented in any language.

Input : 10
Output : 3

Input : 16
Output : 4

Naive solution : Find Square Root of an integer using iteration

To find the square root of an integer n, the simplest approach is to iterate through all the integers starting from 1 until the square of the integer is greater than n. We start the counter with 1. At each step, we check if the square of the counter is less than n. If the condition is satisfied, increment the counter. Once the square of the counter is greater than the given number n, the loop breaks and return the previous value of the counter as the counter must have increment one more time when the loop breaks. We take care of base cases as when the given number is 0 or 1, the algorithm should simply return the given number.

// Simple solution to find square root in C++
#include<bits/stdc++.h>
using namespace std;

int SqrtFloor(int n)
{
   if ((n==0)||(n==1))
      return n;
   int i=1;

   while(i*i <= n)
      i++;
   return i-1;
}

Time Complexity: Theta(root(n))
Aux. Space: O(1)

Efficient solution : Find Square Root of an integer using binary search

We can use binary search to pick the number whose square we are comparing against the given integer n. To find the square root of a number n, we start with a low and high pointer set as 1 and n respectively. We run a loop until low<= high and do the following check in every iteration. We calculate mid of low and the high and check if the square of mid is less than , equal to or greater than n. If the square of mid is equal to n , return mid. If the square of mid is less than n, it means we have to move towards left half. So, we update the high as mid-1. If the square of mid is greater than n, it means we have to move towards right half. Hence, update the low as mid+1. If the integer n is a perfect square than algorithm will return mid .
If the number is not a perfect square the value of mid-1 will be returned, which is the floor of the square root of n. This significantly reduces the no. of steps to find the element as compared to linear search.

Below is the implementation of the binary search method in C++. 

// Binary search based solution to find square root of a number in C++
#include<bits/stdc++.h>
using namespace std;

int SqrtFloor(int n)
{ 
  if((n==0)||(n==1)) #Handle base case
    return n;
  int low = 1, high = n, res = -1;

  while(low <= high)
  {
   int mid = (low+high)/2;
   int msq = mid*mid;

   if(msq == n)
     return mid;
   else if(msq > n)
     high = mid-1; 
   else
     low = mid+1;
     res= mid
  }

  // if n is not a perfect square then return floor(sqrt(n))
  return res;  

}

Lets perform a dry run on example :

  1. Lets, n= 10.
  2. Initialize : low = 1, high = 10
  3. In the 1st Iteration we have, mid = 5, msq= 5*5= 25, high =mid-1= 4, low = 0, res= -1.
  4. In the 2nd Iteration we have, mid = 2, msq= 2*2= 4, high= 4, low =mid+1= 3, res= 2.
  5. In the 3rd Iteration we have, mid = 3, msq= 3*3= 9, high= 4, low =mid+1= 4, res= 3
  6. In the 4th Iteration we have, mid = 4, msq= 4*4= 16, high =mid-1= 3, low = 4, res= 3.
  7. The loop will break when low>high
  8. The value of res will be returned (3 in this case) to the main function.

Time complexity: O(log n). As we have to go to either greater than half the no. or less than half the no. at each step, which is better than Theta(root(n)).
Aux. Space: O(1)

Solve the question here on LeetCode: https://leetcode.com/problems/valid-perfect-square/

Leave a Comment