69. x 的平方根

解法一：二分法

思路：因为是非负整数，x 的平方是单调递增的，所以 x 的一半的平方实际上是大于 x 的。使用二分法可以找到一个相近的位置。

代码中不使用m*m 的原因是为了防止越界。

class Solution {
    fun mySqrt(x: Int): Int {
        if (x == 0 || x == 1) return x
        
        var left = 1
        var right = x
        var res = -1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (mid < x / mid) {
                left = mid + 1
                res = mid
            } else if (mid > x / mid) {
                right = mid - 1
            } else {
                return mid
            }
        }
        return res
    }
}

解法二：牛顿迭代法

传说在一个月黑风高的夜晚… 有人发明了一个算法，欲知后情如何，请看：wiki

class Solution {
    fun mySqrt(x: Int): Int {
        var r = x.toLong()
        while (r * r > x) {
            r = (r + x / r) / 2
        }
        return r.toInt()
    }
}

数学家的伟大成果。

扩展题：367. 有效的完全平方数

思路依旧是二分，只是说得加上浮点匹配，保留精确度才能找到完全平方数。

class Solution {
    fun isPerfectSquare(num: Int): Boolean {
        if (num == 0 || num == 1) return true

        var left = 1
        var right = num

        while (left <= right) {
            val mid = left + (right - left) / 2
            when {
                mid < num * 1.0f / mid -> {
                    left = mid + 1
                }
                mid > num * 1.0f / mid -> {
                    right = mid - 1
                }
                else -> {
                    return true
                }
            }
        }
        return false
    }
}