141. Sqrt(x)

这道题虽然标记easy难度。但是我觉得是十分好的一道题。看似简单的Binary Search但是也暗流涌动

  1. 要比较的并不是mid和left/right比较,而是mid的平方和x的比较
  2. 此题可以翻译成,找到最后一个数字,其平方小于等于x。所以也就是转化成了那类找到match也不结束要缩小范围的,本题就是取右侧边缘
  3. 返回值是int,但是中间数字要用long。如果不小心用了int会溢出而出错误结果。
  4. 循环条件如果写成如下的,记得要在left和right之差1的时候break否则因为我们左右挪的时候都没mid-1或者+1会造成无限循环。还有一种办法就是while(left+1<right)但是我不是太习惯这类写法。

long left = 1;
 long right = x; 
 
 while(left<right){
 if(left+1==right){
 break; //
 }
 
 long mid = (right-left)/2 + left;
 // System.out.println(mid);
 
 if(mid*mid<=x){
 left= mid;
 }
 else{
 right = mid;
 }
 }
 if(right * right <= x){
 return (int) right;
 }
 
 return (int)left;

Show your support

Clapping shows how much you appreciated DeReK’s story.