请实现一个函数，计算一个非负整数的整数平方根，即返回最大的整数 x 使得 x*x

Question

请实现一个函数，计算一个非负整数的整数平方根，即返回最大的整数 x 使得 x*x <= n。要求不调用内置的 sqrt 函数，并说明时间复杂度和边界情况。

Accepted Answer

考察点：考察二分查找或牛顿迭代法实现整数开方及边界处理。回答思路：明确输入输出类型与边界（n=0, n=1） 能正确实现二分查找或牛顿迭代法 分析时间复杂度并处理溢出风险

请实现一个函数，计算一个非负整数的整数平方根，即返回最大的整数 x 使得 x*x <= n。要求不调用内置的 sqrt 函数，并说明时间复杂度和边界情况。