69. x 的平方根

题意：

解题思路：

思路：
二分出最大的 k，满足$k^2$ < x。

PHP代码实现：

class Solution {
    /**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        if ($x == 0 || $x == 1) return $x;
        $low = 1; $high = $x;
        while ($low <= $high) {
            $mid = $low + floor(($high - $low) >> 1);
            if ($mid == floor($x / $mid)) {
                return $mid;
            } else if ($mid > floor($x / $mid)) {
                $high = $mid - 1;
            } else {
                $low = $mid + 1;
                $res = $mid;
            }
        }
        return $res;
    }
}

GO代码实现：

func mySqrt(x int) int {
    left, right := 0, x
    for left <= right {
        mid := left + (right - left) >> 1
        if mid * mid <= x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left - 1
}