C++-写给你一个非负整数-x-计算并返回-x-的-算术平方根-。nn由于返回类型是整数结果只保留-整数部分-小数部分将被-舍去-。

解题思路： 本题考察的是二分查找的思想。我们可以将二分区间设为[0,x]，然后通过二分法不断缩小区间，直到找到最接近x的算术平方根的整数部分。具体操作如下：

1. 初始化左指针为0，右指针为x，并计算中间指针mid
2. 判断mid的平方是否等于x，如果是则直接返回mid
3. 如果mid的平方小于x，则将左指针移到mid右侧，否则将右指针移到mid左侧
4. 重复以上步骤，直到左右指针相遇

代码实现：

class Solution { public: int mySqrt(int x) { if (x < 2) return x; int left = 0, right = x; while (left < right) { int mid = left + (right - left) / 2; if (mid == x / mid) { return mid; } else if (mid < x / mid) { left = mid + 1; } else { right = mid - 1; } } return right; } };

时间复杂度：O(logx)。 空间复杂度：O(1)。