LeetCode Q69: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Easy question at the first glimpse, however, some corner cases can stop you for a long time. Apparently, should solve it using binary search. However, need to change a bit in a few places than normal binary search. For example, in following code, from line 4 -- line 9, we don't wait until l>=h to stop recursion, because, in that case, we may miss a few right solutions. Also, in line 17 and line 19, we don't increase low bound by one or decrease upper bound by one to ensure the middle position is still included in the next recursion. 

	class Solution {
	public:
	long helper(long l, long h, long x){
	if(l==h-1||l==h){
	if(h*h<=x)
	return h;
	else
	return l;
	}
	long m=(l+h)/2;
	if(m*m==x)
	return m;
	if(m*m<x)
	return helper(m, h, x);
	else
	return helper(l, m, x);
	}
	int mySqrt(int x) {
	if(x<=1)
	return x;
	return helper(long(0), long(x/2), long(x));
	}
	};

view raw Q69Sqrtx.cpp hosted with ❤ by GitHub

Round 2 solution:
Using Newton's method, for details, refer to this post:

	class Solution {
	public:
	int mySqrt(int x)
	{
	long r = x;
	while (r*r > x)
	r = (r + x/r) / 2;
	return r;
	}
	};

view raw Q69-2.cpp hosted with ❤ by GitHub