class Solution {
public:
	int mySqrt(int x) {
		/**
		* binary search a from [0, x], where a^2 = x.
		*/
		if (x < 0) return 0;
		return BSearchByLoop(x);
	}

	int BSearch(int x, int start, int end) {
		/**
		* binary search a from [start, end], where a^2 = x.
		* Note: when x is very big, stack overflow exception occurs.
		*
		* 1. if start > end, then return -1;
		* 2. tmp = (start + end) / 2
		* 3. if tmp^2 = x, then return tmp;
		* 4. if tmp^2 < x, then return BSearch(x, tmp + 1, end);
		* 5. if tmp^2 > x, then return BSearch(x, start, tmp - 1);
		*/

		if (0 == x || 1 == x) return x;

		if (start >= end) {
			if (start * start <= x) return start;
			else return start - 1;
		}

		int mid = (start + end) / 2;
		if (mid * mid == x) return mid;
		else if (mid * mid < x) return BSearch(x, mid + 1, end);
		else return BSearch(x, start, mid - 1);
	}

	int BSearchByLoop(int x)
	{
		/*
		1. if 0 == x or 1 == x, then return x;
		2. start = 0, end = x.
		3. if start > end, then return end;
		4. mid = (start + end) / 2;
		5. if mid^2 == x, return mid;
		6. if mid^2 > x, end = mid - 1; jmp 3;
		7. if mid^2 < x, start = mid + 1; jmp 3;
		*/

		if (0 == x || 1 == x) return x;
		int start = 0, end = x;
		while (start <= end)
		{
			long long mid = (end - start) / 2 + start; // mid*mid is probably bigger than 2^32
			if (mid * mid == x) return mid;
			else if (mid * mid > x) end = mid - 1;
			else start = mid + 1;
		}
		return end;
	}
};

版权声明：本文为博主原创文章，未经博主允许不得转载。