题目大意：
x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=69
解题思路分析：
本题的暴力解法是从1到x分别求平方，找到第一个小于等于x的数即可。这样的线性解法时间复杂度为x，如果x非常大的话，效率会很低。因此这类题目需要考虑使用二分查找，查看1和x的中间数mid的平方n，如果n等于x，那么返回mid。如果n小于x并且mid加一的平方大于x，这时也可以返回mid。除此之外，如果n小于x，左指针变为mid加一，反之右指针变为mid-1。
实现代码：
public int mySqrt(int x) {
if(x<=1) return x;
long l=1,r=x;
while(l<=r){
long mid=(l+r)/2;
long n=mid*mid;
if(n==x||n<x&&(mid+1)*(mid+1)>x) return (int)mid;
if(n>x){
r=(int)mid-1;
}else{
l=(int)mid+1;
}
}
return -1;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Sqrt(x).
Memory Usage: 37 MB, less than 5.00% of Java online submissions for Sqrt(x).
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-69-sqrtx-解题思路分析/