使用二分法计算x 的平方根

一、题目

二、代码 

 注意：1.乘法溢出转换成除法计算

           2.最大的初始值设x /2

class Solution {
    public int mySqrt(int x) {
       if(x == 1){
           return 1;
       }
       int left = 1;
       int right = x / 2;
       while(left <= right){
           int mid = (left + right) / 2;
           //防止乘法溢出，转换为除法
           if(mid == x / mid){
               return mid;
           }else if( mid > x / mid){
               right = mid - 1;
           }else{
               left = mid + 1;
           }
       }

       return right;
    }
}