LeetCode——69. x 的平方根

@代码随想录

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4

输出：2

示例 2：

输入：x = 8

输出：2

解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

由于只保留整数部分，舍去小数部分，所以用寻找左边界的方法寻找结果

注意：

1. int 类型数值相乘时很容易导致溢出，用 middle * middle 的值做判断很有可能因为溢出导致不正确的结果。应使用 middle 与 x / middle 做对比，则可以避免溢出。

2. 如果 int 类型计算溢出，系统将会自动向上类型转换做中间数的存储，但是赋值时，由于是 int 型变量接收，所以会直接去后32位作为结果，前面的全部舍去

3. long result = middle * middle
   以上式子，若 middle 是 int 类型，则在计算时默认结果为 int 类型，得到不正确的结果后向上转换为 long 类型，仍然得不到正确的数值
   int middle = 1234567；
   long result = middle * middle；//溢出

   long middle = 1234567；
   long result = middle * middle； //正确结果
   或
   long result = 1234567L * 1234567L；//正确结果
   long result = 1234567 * 1234567；//错误结果
   

代码：

 public class Solution {
           public static int mySqrt(int x) {
               int left = 1;
               int right = x / 2;
               int lb = -1;//求左边界
               while(left <= right){
                   int middle = left + ((right - left) >> 1);
                   if(middle > x / middle){
                       right = middle - 1;
                   }else{
                       left = middle +  1;
                       lb = left;
                   }
               }
               if(x == 0) return 0;
               if(x == 1) return 1;
               return (lb - 1);
       
           }
       }

通过增加更直观的判断条件实现

   class Solution {
   public int mySqrt(int x) {
           int l = 0, r = x;
           if(x == 0) return 0;
           if(x == 1) return 1;
           while(l < r){
               int mid = l + r >> 1;
   
               if((mid  <= x / mid) && ((mid + 1) > x / (mid + 1)))
                   return mid;
               else if(mid <= x / mid)
                   l = mid + 1;
               else
                   r = mid - 1;
           }
           return l;
       }
   };

但要注意，如果不在一开始判断0 、1 两种特殊情况，在计算 x / mid 时有可能出现 x 为 0 的情况，导致程序报错。