本文共 2009 字，大约阅读时间需要 6 分钟。

1. 题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sqrtx

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 示例

3. 思路

将原数不断除以2，获得一个相对接近目标值的开始基数，然后再通过这个开始基数去不断加一，根据平方判断是否能够恰好小于等于目标值的最大数。

4. 遇上的问题

一开始没有思路啊，平方根这个东西，是怎么来的也是莫名其妙，结果算法做出来果然很低级。

再做的过程中会出现平方之后的数超过了int的最大值范围转而变成了负数，导致计算结果出错，可以通过强转long解决。

5. 具体实现代码

自己写的代码

class Solution {
       public int mySqrt(int x) {
           int index = 0;        int sum = 1;        int count = x;        if(x<=1){
   return x;}        //通过除二获得一个开始循环值        while(count>0){
               if(count%2!=0)            index++;            count=count/2;                        if(index==2){
                   sum *=2;                index=0;            }        }        //利用开始循环值逐步加1，再平方比较        for(int i = sum;i<=x;i++){
               if(i*i==x){
                   return i;            }            else if(i*i<0) return i-1;            else if(i*i>=x&&(i-1)*(i-1)

只能说，很笨，建议不要看。看官方的把

6. 学习收获,官方一如既往的妙啊

class Solution {
   	//二分法查询    public int mySqrt(int x) {
           int l = 0, r = x, ans = -1;        while (l <= r) {
           	//确立一个中间值            int mid = l + (r - l) / 2;            //long强转避免平方后超过int类型范围导致比较错误            if ((long) mid * mid <= x) {
               	//保存每一个mid，因为这个mid可能是所求的最大值                ans = mid;                //mid+1,用于减少范围，开始值已经不需要从mid开始了                l = mid + 1;            } else {
             	  //mid+1,用于减少范围，结尾值已经不需要从mid开始了                r = mid - 1;            }        }        return ans;    }}

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

从这一题来看，我已经使用的是遍历的查找，效率慢，二分查找能明显提高执行速度。还是不熟练掌握啊。

官方的题解一是调用函数方法做的，没有细看，题解二是二叉树，题解三就不得了了，用了牛顿迭代法（一种用来快速求零点的方法），零点是啥？是x^2图像和x轴坐标系相交的点，而这个点可以用牛顿迭代法来获得。 emm简单来说就是从图像上一个点做斜线，拿到与x轴交点值，再带入所求图像的方程式，再做切线，求与x轴的交点值，再带入图像方程，不断重复，到最后会取到很相近的两点，就是所求点。

7 题目来源

---

啊，数学，终究还是要和你对上，命理看花，几经重逢~ ------swrici