科技看点|C++题解系列-068 x 的平方根，leetcode 很显然

首先最自然的方案，当然是对对碰。如求10的平方根，我可以从1开始碰， 1*1==1显然不对，一直到4*4==16才发现超出了。于是答案显然是3.
【科技看点|C++题解系列-068 x 的平方根，leetcode】但这种类似穷举的方式显然很不智，既然是查找能碰对的数，肯定二分搜索要快一些。如先看5*5==25,25>10,范围向左缩小，并继续中分，有3*3==9 ， 9<10 ，范围向右缩小，并继续中分，有4*4==16,16>10,right==3,left==4.结束。
那结果应该取哪一次的middle呢？显然因为咱们是integer的运算，取小不取大， 3可以是结果， 4决计不是。故有：
if(mid<=x/mid)ret=mid;整个程序非常简单，而且高效AC:
intl=1,r=x,ret=0;while(l<=r){intm=(l+r)>>1;if(m<=x/m){l=m+1;ret=m;}elser=m-1;}returnret;这道题算是告一段落，但我们其实占了integer的便宜，假使要实现的是floatsqrtf(floatx),我们可能需要考虑一下使用著名的牛顿迭代了。这就基本演变为一道数学题了。具体可见Matrix67这篇博文中的解释。
#include#includefloatsqrtf(floatx){floatret;for(floatf=1.f;true;f=ret){ret=(f+x/f)/2;if(std::abs(f-ret)<FLT_MIN)break;}returnret;}