class Solution {
public int mySqrt(int x) {
int count =0 ;
int val = count *count ;
while(val<=x&&val>=0)
{
count++;
val=count*count;
}
return count==0?0:count-1;
}
}
一开始我的想法是直接相乘到大于X取此时的count-1就好了，事实证明这个方法的效率比较低，我的算法直接排到了倒数百分之五。那么怎么写会比较快呢？看了一下discuss，顺序的排列可以考虑二分法，二分跳出的条件是mid>(x/mid)&&mid-1<(x/(mid-1)).这样写的话，由于剔除了原有的乘法操作。
改进后的代码：跑的快多了 比香港记者还快。
class Solution {
public int mySqrt(int x) {
if(x==0) return 0;
int lo = 1 ;
int hi = x;
int mid = 0 ;
while(lo<=hi)
{
mid = lo+(hi-lo)/2;
if(mid==x/mid)
return mid;
else if(mid>x/mid)
{
if(mid-1<x/(mid-1))
break;
else
hi=mid-1;
}
else
lo=mid+1;
}
return mid-1;
}
}
