X的平方根
题目描述
给你一个非负整数 x ，计算并返回 x 的算术平方根 。
由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是2.82842... 由于返回类型是整数,小数部分将被舍去。
思路
题目要求
- 求非负整数的算术平方根
- 保留整数
算术平方根：是一个非负整数
一个数x的算术平方根一定在0~x/2，升序数组，考虑使用二分查找法找到目标元素
注意
在二分查找过程中有三种情况
- 如果这个整数的平方等于输入整数，那么我们就找到了这个整数；
- 如果这个整数的平方大于输入整数，那么这个整数肯定不是我们要找的那个数；
- 如果这个整数的平方小于输入整数，那么这个整数可能是我们要找的那个数(算术平方根为小数时只保留整数)。
若算术平方根是小数，则最后一轮循环中，mid是第一个大于x/mid的值，所以在左区间寻找，执行right = mid -1，此时right < left，结束循环，right就是只保留整数的算术平方根(通过三个指针的移动理解)。
代码
Go
func mySqrt(x int) int { left, right := 1, x/2 if x <= 1 { return x } for left <= right { 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 }
