1. 概述

实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

输入: 8

输出: 2

说明: 8 的平方根是 2.82842…, 

  1.  由于返回类型是整数，小数部分将被舍去。

2. 解题

<?php
class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */
    public function mySqrt($x) {
        if ($x <= 0) {
            return 0;
        }

        $left = 1;
        $right = $x;
        $close = 0;
        while ($left < $right) {
            $mix = $left + floor(($right - $left) / 2);
            $square = $mix * $mix;
            if ($square > $x) {
                $right = $mix - 1;
            } elseif ($square == $x) {
                $close = $mix;
                break;
            } else {
                $left = $mix + 1;
                $oriClose = $x - $close * $close;
                $newClose = $x - $mix * $mix;
                $close = min($oriClose, $newClose) == $oriClose ? $close : $mix;
            }
        }

        return $close;
    }
}

$x = 8;
$cls = new Solution();
$r = $cls->mySqrt($x);
echo $r;