LC69.Sqrtx

给你一个非负整数x，不使用内建函数或运算符，求x的整数平方根

//方法1
//该问题可转化为 求 n^2 <= x，求n的最大值
//使用二分查找

class Solution_1
{
public:
	int mySqrt(int x)
	{
		if (x < 2) return x;
		int l = 0, r = x / 2, mid = 0;
		while (l <= r)
		{
			mid = (l + r) / 2;
			if ((long long)mid * mid <= x)
			{
				l = mid + 1;
			}
			else r = mid - 1;
		}
		return l - 1;
	}
};

//方法2
//使用指数函数和对数函数替代平方根函数
//sqrt(x)可以变换为 e^(0.5lnx)

#include <cmath>
class Solution_2
{
public:
	int mySqrt(int x)
	{
		if (x == 0) return 0;
		int ans = exp(0.5 * log(x));
		return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);//计算机无法存储准确的浮点数，需要判断正确答案
	}
};

//方法3
//牛顿迭代
class Solution_3
{
public:
	int mySqrt(int x)
	{
		if (x == 0) return 0;

		double C = x, x0 = x;
		while (true)
		{
			double xi = 0.5 * (x0 + C / x0);
			if (fabs(x0 = xi) < 1e-7) break;
			x0 = xi;
		}
		return int(x0);
	}
};