In this article, we have discussed how to find square root of a number using binary search.

Table of contents:

1. Introduction to Binary Search
2. Iterative and recursive version of binary search
3. Finding square root using binary search
4. Time and Space Complexity

Pre-requisites:

• Binary search

Finding Square Root of a Number using Binary Search

While searching for an element in an array, we generally go through all the elements and if the element is found, we will return the element; otherwise, we say the element is not found. This type of search is known as linear search, and its time complexity is O(n), which we reduce here by using binary search.

Binary Search

While performing binary search, we should ensure that the array is sorted. Binary search follows the divide and conquer approach where the list is divided into two halves and the item is compared with the middle element each time. If the middle element is less than the element to be searched, then we search for the element in the first half of the list; otherwise, we search for the element in the second half of the list. The point at which middle element is equal to the searched element we say search is successful and return the value.

If the given array is not sorted then first sort the array and then apply binary search method.

We generally have two methods of binary search:

Iterative method

Input:

#include <bits/stdc++.h>

using namespace std;
 //iterative method for binary search
int binarySearch(int arr[], int l, int r, int x)
{

    while (l<= r) {

        int m = l + (r - l) / 2;
 
        //checing mid value
        if (arr[m] == x)

            return m;
 

        //if x is greater than mid value we search only in right half and ignore left half

        if (arr[m] < x)

            l = m + 1;
 
       //if x is lesser than mid value we search only in left half and ignore right half
        else
            r = m - 1;
    }
    // if element is not present we return -1
    return -1;
}

int main(void)
{
    //as we have discussed we take sorted array
    int arr[] = { 12, 24,36,48,50 };

    int x = 36;

    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearch(arr, 0, n - 1, x);
    if(result == -1)
            cout << "Element is not in the array";
    else
    
            cout << "Element is present at index " << result;
    return 0;
}

Output:

Element is present at index 2
--------------------------------
Process exited after 0.0941 seconds with return value 0
Press any key to continue . . .

Recursive method (Divide and conquer approach)

Input

#include <bits/stdc++.h>
using namespace std;
 // recursive method for binary search
int binarySearch(int arr[], int l, int r, int x)
{

    if (r >= l) {
          int mid = l + (r - l) / 2;
           //cheching whether if element is present at middle
    if (arr[mid] == x)
        return mid;
        //if x is lesser than mid value we search only in left half and ignore right half
	if (arr[mid] > x)
        return binarySearch(arr, l, mid - 1, x);
         //if x is greater than mid value we search only in right half and ignore left half
        return binarySearch(arr, mid + 1, r, x);
    }
       // if element is not found then we return -1
    return -1;
}
 int main(void)
{

    int arr[] = { 12, 36, 48, 56,60 };
    int x = 60;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
   if(result == -1)
            cout << "Element is not in the array";
    else
            cout << "Element is present at index " << result;
    return 0;
}

Output:

Element is present at index 4
--------------------------------
Process exited after 0.09934 seconds with return value 0
Press any key to continue . . .                

Finding Square Root of a Number using Binary Search

Here, if a given number is a perfect square, we return its exact square root value. If it is not a perfect square, we return the floor value of that.

Algorithm

Step 1: We know we find square root values for only positive numbers and set the start and end values.

Step 2: As we know, the required square root value will always be less than the given value. Hence, we take the end values as the number itself and calculate the mid values by taking an average of the start and end values.

Note: The mid value will be changed each time it enters the loop.

Step 3: Next, we compute the square of the midpoint.If it is less than the value for which we find square root, then we will check only the right half of the array by updating the lower value to mid+1. If the value is greater than the value for which we find square root, then we will search in the left half of the array and update the higher value that is end=mid-1.

Step 4: Now, after finding the integral part, we find the fractional part by incrementing it by 0.1 each time and finding the value up to the required precision.

Step 5: Finally, the answer is returned.

Example:

Input:

#include <bits/stdc++.h>

using namespace std;
float squareRoot(int x, int precision)
{
    int start = 1, end = x;
    int mid;
    float ans;
    
    while (start <= end) {
           //calculating mid value
        mid = (start + end) / 2;
        //if square of mid is equal to x then we return mid value
        if (mid * mid == x) {

            ans = mid;

            break;

        }
        //if square of mid is less than x then we search in only right half of array
        if (mid * mid < x) {

            start = mid + 1;

            ans = mid;

        }
        ////if square of mid is greater than x then we search in only left half of array
        else {

            end = mid - 1;

        }   

    }
    float increment = 0.1;
 //caluculating precision and this loop ends if ans square is greater than x
    for (int i = 0; i < precision; i++) {

        while (ans * ans <= x) {
             
            ans += increment;

        }
        ans = ans - increment;

        increment = increment / 10;

    }

    return ans;
}
int main()
{
    cout << squareRoot(27, 3) << endl;
    return 0;
}

Output

5.196

--------------------------------
Process exited after 0.08316 seconds with return value 0
Press any key to continue . . .

Explanation of above code

• As such, we are finding the square root value of 27. Hence, the end value is equal to 27. Now we calculate the mid value (27+1/2), which is 14, and the square of 14 is less than the number 27. Here we change the value of end to = 13 (14-1), so the square is less than the number. The loop repeats until a number where the square of mid is less than 27, that is, 25, and then ans = 5.
• Now we calculate precision by using a while loop where the loop ends if the square of the ANS value is less than x.

Time and Space Complexity

Time complexity:

• As we know, when performing binary search, we split an array in half and search only in one half of the array each time, resulting in a logarithmic time complexity.The time required to calculate the square root value is O(log(x)) and constant for computing fraction part of square root value hence overall time complexity is O(log(x)+precision) which is equal to O(log(x)).

Space complexity

• Space complexity is in the order of O(1) as constant space is required here.

Questions:

1. Can you improve this binary search? Write the algorithm and calculate the time and space complexity.
2. What are the various methods for finding the square root of a number? Justify which is the better solution.