Leetcode - 69. Sqrt(x)

Leetcode - 69. 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.

Solution

func mySqrt(x int) int {
    if x<2{
        return x
    }

    minVal, maxVal := 1, x/2

    for minVal<=maxVal{
        midVal := (minVal+maxVal)/2

        midSquareVal := midVal*midVal

        if midSquareVal == x{
            return midVal
        }
        if midSquareVal>x{
            maxVal = midVal-1
        }else{
            minVal = midVal+1
        }
    }
    return maxVal
}