2 solutions: bin-search and Newton iteration.
class Solution { public: int _sqrt(long long tgt, long long i0, long long i1) { long long cand = (i0 + i1) / 2; if (cand * cand == tgt) return cand; if (cand * cand > tgt) return _sqrt(tgt, i0, cand); else if(cand * cand < tgt) { if((cand + 1)*(cand + 1) > tgt) return cand; if((cand + 1)*(cand + 1) == tgt) return cand + 1; return _sqrt(tgt, cand + 1, i1); } } int sqrt(int x) { if (x == 1) return 1; return _sqrt(x, 1, x/2); } };
LeetCode "Sqrt(x)",布布扣,bubuko.com
原文:http://www.cnblogs.com/tonix/p/3862126.html