Description

Sqrt(x)

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:

1 2	Input: 4 Output: 2

Example 2:

1 2 3 4

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

整型“开方”

根据题意，mySqrt(x) = floor(sqrt(x))

Solution

使用二分法进行查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func mySqrt(x int) int {
    if x == 0 {
        return 0
    }
    left, right := 1, x/2

    for left < right {
        m := right - (right-left)/2
        if m*m > x {
            right = m - 1
        } else {
            left = m
        }
    }

    return left
}

Similar Problem

• 50. Pow(x, n)