Question

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

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

Example 1:

Input: 4
Output: 2

Example 2:

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

Solution

Use binary search from 1 to x, and return when i * i == x or binary search yields two adjacent number i, i + 1 with i * i < x < (i + 1) * (i + 1). Then return i.

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0 or x == 1:
            return x

        min, max = 1, x
        while max - min > 1:
            mid = (min + max) // 2
            mid_2 = mid * mid
            if mid_2 > x:
                max = mid
            elif mid_2 < x:
                min = mid
            else:
                return mid

        return min