HPE VO 面试真题解析：Truncated Integer Square Root（整数平方根）

Given a non-negative integer a, compute and return the truncated integer of the square root of a.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(), 0.5, or a ** 0.5.

Example 1:

Input: a = 4
Output: 2

Example 2:

Input: a = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= a <= 2**31 - 1

这道题要求在不能直接使用幂运算或内置开方函数的前提下，返回非负整数 a 的整数平方根，也就是向下取整后的 sqrt(a)。最常见的做法是使用二分查找：在区间 [0, a] 中寻找满足 mid*mid <= a 的最大值；当 mid*mid 过大时向左收缩，过小时向右收缩。由于结果只需要截断后的整数部分，因此不需要处理小数精度问题。对于 a=4，答案是 2；对于 a=8，sqrt(8) 约为 2.82842，截断后仍然是 2。