# 69 - Sqrt(x)

解法一 - Binary Search

這題基本想法應該沒什麼問題，不過要注意幾個點：

1. x == 0 的時候就直接 return 0

2. 因為 mid*mid 可能會 overflow，所以要用 long

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0;
        long l = 1, mid, r = x;

        while(l+1 < r) {
            mid = l + (r-l)/2;

            if(mid*mid == x) return mid;
            else if(mid*mid > x) r = mid;
            else l = mid;
        }

        return l;
    }
};