[LeetCode] Sqrt(x)

Problem: Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example:

Input: x = 4
Output: 2

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

1. 0 <= x <= 2^31 - 1

Approach: The obvious approach is to have a loop say i = 1 to x and if we find i * i is equal to x then i is our answer. If x is not a perfect square then in the loop whenever we see the first time i * i is more than x then return i - 1. 

Let's try to do better as here we are searching if we see the range is 1 to x and in sorted order, we can apply binary search here. You can just look at the code to understand the rest.

Implementation in C#:

    public int MySqrt(int x) 

    {

        if (x <= 3)

        {

            return x == 0 ? 0 : 1;

        }        

        long low = 2, high = (long)(x / 2);

        while (low <= high)

        {

            long mid = low + ((high - low) / 2);

            // Take long as mid * mid can overflow.

            long sq = mid * mid;

            if (sq == x)

            {

                return (int)mid;

            }

            else if (sq < x)

            {

                low = mid + 1;

            }

            else

            {

                high = mid - 1;

            }

        }

        return (int)high;

    }

Complexity: O(logx)