Square root an integer using Binary search

The idea is to find the largest integer i whose square is less than or equal to the given number. The values of i * i is monotonically increasing, so the problem can be solved using binary search.

Below is the implementation of the above idea:

Base cases for the given problem are when the given number is 0 or 1, then return X;
Create some variables, for storing the lower bound say l = 0, and for upper bound r = X / 2 (i.e, The floor of the square root of x cannot be more than x/2 when x > 1).
Run a loop until l <= r, the search space vanishes
Check if the square of mid (mid = (l + r)/2 ) is less than or equal to X, If yes then search for a larger value in the second half of the search space, i.e l = mid + 1, update ans = mid
Else if the square of mid is more than X then search for a smaller value in the first half of the search space, i.e r = mid – 1
Finally, Return the ans

Below is the implementation of the above approach:

C++

#include <iostream>
 
using namespace std;
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
        return x;
 
    // Do Binary Search for floor(sqrt(x))
    int start = 1, end = x / 2, ans;
    while (start <= end) {
        int mid = (start + end) / 2;
 
        // If x is a perfect square
        int sqr = mid * mid;
        if (sqr == x)
            return mid;
 
        // Since we need floor, we update answer when
        // mid*mid is smaller than x, and move closer to
        // sqrt(x)
 
        /*
           if(mid*mid<=x)
                   {
                           start = mid+1;
                           ans = mid;
                   }
            Here basically if we multiply mid with itself so
           there will be integer overflow which will throw
           tle for larger input so to overcome this
           situation we can use long or we can just divide
            the number by mid which is same as checking
           mid*mid < x
 
           */
        if (sqr <= x) {
            start = mid + 1;
            ans = mid;
        }
        else // If mid*mid is greater than x
            end = mid - 1;
    }
    return ans;
}
 
// Driver program
int main()
{
    int x = 11;
    cout << floorSqrt(x) << endl;
    return 0;
}

C

#include <math.h>
#include <stdio.h>
 
int floorSqrt(int x)
{
    // Base Cases
    if (x == 0 || x == 1)
        return x;
 
    // Do Binary Search for floor(sqrt(x))
    long start = 1, end = x / 2, ans = 0;
    while (start <= end) {
        int mid = (start + end) / 2;
 
        // If x is a perfect square
        if (mid * mid == x)
            return (int)mid;
 
        // Since we need floor, we update answer when
        // mid*mid is smaller than x, and move closer to
        // sqrt(x)
        if (mid * mid < x) {
            start = mid + 1;
            ans = mid;
        }
        else // If mid*mid is greater than x
            end = mid - 1;
    }
    return (int)ans;
}
 
// Driver Method
int main()
{
    int x = 11;
    printf("%d\n", floorSqrt(x));
}
 
// Contributed by lalith kumar.g

Java

// A Java program to find floor(sqrt(x)
public class Test {
    public static int floorSqrt(int x)
    {
        // Base Cases
        if (x == 0 || x == 1)
            return x;
 
        // Do Binary Search for floor(sqrt(x))
        long start = 1, end = x / 2, ans = 0;
        while (start <= end) {
            long mid = (start + end) / 2;
 
            // If x is a perfect square
            if (mid * mid == x)
                return (int)mid;
 
            // Since we need floor, we update answer when
            // mid*mid is smaller than x, and move closer to
            // sqrt(x)
            if (mid * mid < x) {
                start = mid + 1;
                ans = mid;
            }
            else // If mid*mid is greater than x
                end = mid - 1;
        }
        return (int)ans;
    }
 
    // Driver Method
    public static void main(String args[])
    {
        int x = 11;
        System.out.println(floorSqrt(x));
    }
}
// Contributed by InnerPeace

Python3

# Python 3 program to find floor(sqrt(x)
 
# Returns floor of square root of x
 
 
def floorSqrt(x):
 
    # Base cases
    if (x == 0 or x == 1):
        return x
 
    # Do Binary Search for floor(sqrt(x))
    start = 1
    end = x//2
    while (start <= end):
        mid = (start + end) // 2
 
        # If x is a perfect square
        if (mid*mid == x):
            return mid
 
        # Since we need floor, we update
        # answer when mid*mid is smaller
        # than x, and move closer to sqrt(x)
        if (mid * mid < x):
            start = mid + 1
            ans = mid
 
        else:
 
            # If mid*mid is greater than x
            end = mid-1
 
    return ans
 
 
# driver code
x = 11
print(floorSqrt(x))
 
# This code is contributed by Nikita Tiwari.

C#

// A C# program to
// find floor(sqrt(x)
using System;
 
class GFG {
    public static int floorSqrt(int x)
    {
        // Base Cases
        if (x == 0 || x == 1)
            return x;
 
        // Do Binary Search
        // for floor(sqrt(x))
        int start = 1, end = x / 2, ans = 0;
        while (start <= end) {
            int mid = (start + end) / 2;
 
            // If x is a
            // perfect square
            if (mid * mid == x)
                return mid;
 
            // Since we need floor, we
            // update answer when mid *
            // mid is smaller than x,
            // and move closer to sqrt(x)
            if (mid * mid < x) {
                start = mid + 1;
                ans = mid;
            }
 
            // If mid*mid is
            // greater than x
            else
                end = mid - 1;
        }
        return ans;
    }
 
    // Driver Code
    static public void Main()
    {
        int x = 11;
        Console.WriteLine(floorSqrt(x));
    }
}
 
// This code is Contributed by m_kit

PHP

<?php
// A PHP program to find floor(sqrt(x)
 
// Returns floor of 
// square root of x         
function floorSqrt($x) 
{ 
    // Base cases
    if ($x == 0 || $x == 1) 
    return $x;
 
    // Do Binary Search 
    // for floor(sqrt(x))
    $start = 1; $end = $x/2; $ans; 
    while ($start <= $end) 
    { 
        $mid = ($start + $end) / 2;
 
        // If x is a perfect square
        if ($mid * $mid == $x)
            return $mid;
 
        // Since we need floor, we update 
        // answer when mid*mid is  smaller
        // than x, and move closer to sqrt(x)
        if ($mid * $mid < $x) 
        {
            $start = $mid + 1;
            $ans = $mid;
        } 
         
        // If mid*mid is 
        // greater than x
        else
            $end = $mid-1;     
    }
    return $ans;
}
 
// Driver Code
$x = 11;
echo floorSqrt($x), "\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
    // A Javascript program to find floor(sqrt(x)
 
// Returns floor of 
// square root of x         
function floorSqrt(x) 
{ 
    // Base cases
    if (x == 0 || x == 1) 
    return x;
 
    // Do Binary Search 
    // for floor(sqrt(x))
    let start = 1; 
    let end = x/2; 
    let ans; 
    while (start <= end) 
    { 
        let mid = (start + end) / 2;
 
        // If x is a perfect square
        if (mid * mid == x)
            return mid;
 
        // Since we need floor, we update 
        // answer when mid*mid is  smaller
        // than x, and move closer to sqrt(x)
        if (mid * mid < x) 
        {
            start = mid + 1;
            ans = mid;
        } 
         
        // If mid*mid is 
        // greater than x
        else
            end = mid-1;     
    }
    return ans;
}
 
// Driver Code
let x = 11;
document.write(floorSqrt(x) +  "<br>");
 
// This code is contributed by _saurabh_jaiswal
</script>

Output

Complexity Analysis:

Time Complexity: O(log(X)).
Auxiliary Space: O(1).

Thanks to Gaurav Ahirwar for suggesting the above method.

Square root of an integer

Given an integer X, find its square root. If X is not a perfect square, then return floor(√x).

Examples :

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2.

Input: x = 11
Output: 3
Explanation: The square root of 11 lies in between 3 and 4 so floor of the square root is 3.

Naive Approach: To find the floor of the square root, try with all-natural numbers starting from 1. Continue incrementing the number until the square of that number is greater than the given number.

Follow the steps below to implement the above idea

Create a variable (counter) i and take care of some base cases, (i.e when the given number is 0 or 1).
Run a loop until i*i <= n, where n is the given number. Increment i by 1.
The floor of the square root of the number is i – 1

Below is the implementation of the above approach:

C++

// A C++ program to find floor(sqrt(x)
#include <bits/stdc++.h>
using namespace std;
 
// Returns floor of square root of x
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
        return x;
 
    // Starting from 1, try all numbers until
    // i*i is greater than or equal to x.
    int i = 1, result = 1;
    while (result <= x) {
        i++;
        result = i * i;
    }
    return i - 1;
}
 
// Driver program
int main()
{
    int x = 11;
    cout << floorSqrt(x) << endl;
    return 0;
}

C

#include <stdio.h>
 
// Returns floor of square root of x
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
        return x;
 
    // Starting from 1, try all numbers until
    // i*i is greater than or equal to x.
    int i = 1, result = 1;
    while (result <= x) {
        i++;
        result = i * i;
    }
    return i - 1;
}
 
// Driver program
int main()
{
    int x = 11;
    printf("%d\n", floorSqrt(x));
    return 0;
}
// code is contributed by lalith kumar.g

Java

// A Java program to find floor(sqrt(x))
 
class GFG {
 
    // Returns floor of square root of x
    static int floorSqrt(int x)
    {
        // Base cases
        if (x == 0 || x == 1)
            return x;
 
        // Starting from 1, try all numbers until
        // i*i is greater than or equal to x.
        int i = 1, result = 1;
 
        while (result <= x) {
            i++;
            result = i * i;
        }
        return i - 1;
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int x = 11;
        System.out.print(floorSqrt(x));
    }
}
 
// This code is contributed by Smitha Dinesh Semwal.

Python3

# Python3 program to find floor(sqrt(x)
 
# Returns floor of square root of x
 
 
def floorSqrt(x):
 
    # Base cases
    if (x == 0 or x == 1):
        return x
 
    # Starting from 1, try all numbers until
    # i*i is greater than or equal to x.
    i = 1
    result = 1
    while (result <= x):
 
        i += 1
        result = i * i
 
    return i - 1
 
 
# Driver Code
x = 11
print(floorSqrt(x))
 
# This code is contributed by Smitha Dinesh Semwal.

C#

// A C# program to
// find floor(sqrt(x))
using System;
 
class GFG {
    // Returns floor of
    // square root of x
    static int floorSqrt(int x)
    {
        // Base cases
        if (x == 0 || x == 1)
            return x;
 
        // Starting from 1, try all
        // numbers until i*i is
        // greater than or equal to x.
        int i = 1, result = 1;
 
        while (result <= x) {
            i++;
            result = i * i;
        }
        return i - 1;
    }
 
    // Driver Code
    static public void Main()
    {
        int x = 11;
        Console.WriteLine(floorSqrt(x));
    }
}
 
// This code is contributed by ajit

PHP

<?php
// A PHP program to find floor(sqrt(x)
 
// Returns floor of square root of x
function floorSqrt($x)
{
    // Base cases
    if ($x == 0 || $x == 1)
    return $x;
 
    // Starting from 1, try all 
    // numbers until i*i is 
    // greater than or equal to x.
    $i = 1;
    $result = 1;
    while ($result <= $x)
    {
        $i++;
        $result = $i * $i;
    }
    return $i - 1;
}
 
// Driver Code
$x = 11;
echo floorSqrt($x), "\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// A Javascript program to find floor(sqrt(x)
 
// Returns floor of square root of x
function floorSqrt(x)
{
     
    // Base cases
    if (x == 0 || x == 1)
        return x;
 
    // Starting from 1, try all
    // numbers until i*i is
    // greater than or equal to x.
    let i = 1;
    let result = 1;
     
    while (result <= x)
    {
        i++;
        result = i * i;
    }
    return i - 1;
}
 
// Driver Code
let x = 11;
document.write(floorSqrt(x));
 
// This code is contributed by mohan
 
</script>

Output

Complexity Analysis:

Time Complexity: O(√X). Only one traversal of the solution is needed, so the time complexity is O(√X).
Auxiliary Space: O(1).

Thanks, Fattepur Mahesh for suggesting this solution.

Square root an integer using Binary search

C++

C

Java

Python3

C#

PHP

Javascript

Square root of an integer

C++

C

Java

Python3

C#

PHP

Javascript

Categories

Contact US

Square root an integer using Binary search

C++

C

Java

Python3

C#

PHP

Javascript

Square root of an integer

C++

C

Java

Python3

C#

PHP

Javascript

Similar Reads

Categories

Contact US