Binary Search - Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

1 <= nums.length <= 2³¹-1

Solution 1 - Using binary search

In the problem statement, it is mentioned that we cannot use any inbuilt functions, and in case if the answer has decimals we will need to round it down to nearest integer. so in this approach, what we will do is using 1 and x as left and right boundaries, we will apply Binary Search algorithm.

We will compute the mid element and then calculates its square, based on this value we can draw three conclusions.

If the square value is equal to x, then return the mid value.
If the square value is greater than x, this means that the target lies on left side, so we will update right value to mid-1.
If the square value is less than x, this means that the target lies on right side, so we will update left value to mid+1.

If the answer is not found, we will return right value, because when the square value is greater than x we will adjust it to mid-1, so it already have nearest lower bound integer.

public class Sqrt { static int mySqrt(int x) { int left = 1; int right = x; while(left <= right) { int mid = left + (right - left) /2; long square = (long)mid * mid; if(square == x) { return mid; } else if(square > x) { right = mid -1; } else { left = mid+1; } } return right; } public static void main(String[] args) { System.out.println(mySqrt(4)); System.out.println(mySqrt(8)); System.out.println(mySqrt(2147395599)); } }

Complexity Analysis:

Time complexity: Above code runs in O(log n) time where n is the length of input number x.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: