## Sqrt(x)練習
這題我覺得超難的，如果不是一開始就知道這題是[binary search](https://hackmd.io/@er0M3STVTRW2uR3r_2A16g/Sy77SHRIZl)的衍生題，我應該會完全失去方向，但就算知道了，要寫出來其實也不容易。

## 解法

class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        if($x<2){
            return $x;
        }
        
        $left=1;
        $right=$x;
        while($left<=$right){
            $mid=intdiv(($left+$right),2);
            $square=$mid*$mid;
            if($square==$x){
                return $mid;
            }
            if($square<$x){
                $left=$mid+1;
            }elseif($square>$x){
                $right=$mid-1;
            }
        }

        return $right;
    }
}

## 說明
跟binary search一樣，需要先設定搜尋的邊界條件。

比較不一樣的地方是最後返回的值是right。原因是為了要求得迴圈內的臨界值，而while迴圈條件結束的條件便是left=right+1的時候，而中間若是mid有符合條件，則return mid，自動結束迴圈。

至於為什麼不先把right做intdiv(x,2)的處理，原因是如果x是1的話，right會變成0，進而導致迴圈無法進入。