class Solution {
public:
int mySqrt(int x) {
long long v = x;
while(v * v > x)
v = (v + (x / v)) >> 1;
return v;
}
};
Newton's method：just need 4 simple lines. (C++)

@Irving_cl It is meaningless to talk about time complexity of Newton's method. It is about numerical analysis and the convergence rate is used to describe its performance, not time complexity. Thought very hard to analyze the time complexity, we know it is faster than binary search.