###### tags: `LeetCode` `Binary Search` `Easy`
# LeetCode #69 [Sqrt(x)](https://leetcode.com/problems/sqrtx/)
### (Easy)

給你一個非負整數 x ，計算並返回 x 的 算術平方根 。

由於返回類型是整數，結果只保留 整數部分 ，小數部分將被 捨去 。

注意：不允許使用任何內置指數函數和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

---
每次計算中值的平方是否大於目標, 若是則將右值改為中值-1, 否則左值改為中值(左閉右閉)。

注意整數溢位。

---

class Solution {
public:
    int mySqrt(int x) {
        long l=0, r=x;
        while(l<r){
            long m=l+(r-l+1)/2;
            if(m>x/m)r=m-1;
            else l=m;
        }
        return (int)l;
    }
};