leetcode sqrt(x) 不用库函数求平方根

题目要求

实现sqrt (int x)操作，计算并返回根号x。

主要思路

1、最先想到遍历操作，O（n）的时间，符合就返回。
2、更好一点的办法是二分查找，能让时间减少到O（logn），这里有个点需要注意右端从x/2开始，另外在判断时不能用r*r > x 因为r*r非常容易溢出。 我们通常用除法来代替乘法操作。
3、牛顿法，由高到低迭代逼近，会让人眼前一亮。

主要代码，二分法

class Solution {
    
public:int sqrt(int x) {
    if(x<2)return x;long left = 1;//1开始long right = x/2;//右端从x/2开始long mid, last_mid;while(left<=right){
    mid = left + (right-left)/2;if(x/mid> mid) // 不用x > mid * mid 会溢出{
    left = mid + 1;last_mid = mid; //若最后没找到，要返回一个最接近的。}   else if(x/mid<mid)right = mid - 1;elsereturn mid;}return last_mid;}
};

主要代码，牛顿法

class Solution {
    
public:int sqrt(int x) {
    long r = x;while(x/r<r)//根据平方根找到第一个比x小的数r = (r + x/r)/2;return r;}
};