当前位置：
  1. 首页
  2. 拿捏算法面试
  3. 问题详情

【作业2】求 x 平方根的上界

对应课程链接：拿捏算法面试:5. LeetCode69.x的平方根.

在 x 的平方根中，我们求解的是下界，也就是舍弃了小数点部分，这个作业中，我们要求 x 平方根的上界哦，比如当 x = 8 时，x 的平方根大约是 2.8，那我们的答案就是 3，也就是求上界，作业要求：

1、给出秋 x 平方根上限的题解，我这里统一一下方法名，如下

int myUpperSqrt(int x){

}

注意点：
1、当 left = mid 会出现死循环，但是当 right = mid 时并不会出现死循环。
2、mid * mid < x 时，那么 mid 就不可能是我们要找的目标数。 PS：如果你不知道怎么打卡，可以看这里：打卡细则

shuaidi
784 40

共以下 38 个回答

  • 幽小皮 永久会员 2024年3月29日 下午6:34

    class ArrayTest {
    int myUpperSqrt(int x) {
    int l = 0;
    int r = x;
    int mid = 0;
    while(l <= r){
    /修改了一下最后输出条件/
    if(r – l <= 1){
    return l * l < x ? r : l;
    }
    mid = l + (r – l) / 2;
    if((long)midmid < x){
    l = mid+1;
    }else if((long)mid    mid > x){
    r = mid;
    }else{
    return mid;
    }
    }
    return mid;
    }
    }
    “`java

    0 赞同 0 条回复
  • 开心果🍅 永久会员 2024年3月26日 下午10:07 
    class Solution {
    public int mySqrt(int x) {

        /*
        先进行分析 化简为繁

        1.找到mid，比较mid
        注意 这里是找到x的上边界 若是2.8则返回3，所以l r  应该是 l=mid+1，r=mid

        1.1 mid*mid ==x 直接返回
        1.2 mid*mid > x r = mid
        1.3 mid*mid < x l = mid+1
        2.循环条件 l < r 
            当存在例如8的平方根时，会在3这个值进行返回
            所以 if（ r-l<=1）
            进行一个值的返回
        3. 否则返回-1
        */
        int l = 0;
        int r = x;
        while(l<=r){

            if(r-l<=1){
                return l;
            }
            int mid = l+(r-l)/2;
            if((long)mid*mid>x){
                r = mid;
            }
            else if((long)mid*mid
    0 赞同 0 条回复
  • heathhou 普通 2024年3月3日 下午8:21 
    class Solution {
public:
    int mySqrt(int x) {
        int l = 0;
        int r = x;
        int ans = -1;
        while(l <= r){
            if(l == r){
                return l;
            }
            int mid = l + (r - l) / 2;

            if( (long long)mid * mid  < x){
                // 此时mid不可能是需要找的数，更新 l=mid+1 
                l = mid + 1;
            }else if((long long) mid * mid > x){
                // 此时mid可能是需要找的数，更新 r=mid
                r = mid;
            }else{
                return mid;
            }
        }

        return ans;
    }
};
    0 赞同 0 条回复
  • ？ 普通 2024年3月3日 下午12:01

    打卡

    class Solution {
public:
    int mySupperSqrt(int x) {
       if(x <= 1) return x;
        int l , r,m;
        l = 2;
        r = x;
        while(l <= r)
        {
            int mid = l + (r - l) / 2;
            m = mid + 1;
            if((long)mid *mid < x && (long)m * m > x) return m;
            else if((long)mid * mid < x) l = mid + 1;
            else if((long) mid * mid > x) r = mid - 1;
            else return mid;
        }
        return 0;
    }
};
    0 赞同 0 条回复
  • 塔底的仰望 永久会员 2023年10月12日 下午3:02

    即寻找第一个大于x或最后一个等于x的元素

    class Solution {
    public int myUpperSqrt(int x) {
        if (x <= 1) {
            return x;
        }
        long l = 1, r = x;
        while (l < r) {
            long mid = (r - l) / 2 + l;
            long val = mid * mid;
            if (mid * mid > x) {
                r = mid;
            } else if (mid * mid == x){
                return (int) mid;
            } else {  // < x
                l = mid + 1;
            }
        }

        return (int)l;
    }
}
    0 赞同 0 条回复
  • smiler 永久会员 2023年9月26日 上午11:55

    以下是代码

    public int mySqrt(int x) {
        int l = 0, r = x;
        while (l <= r) {
            int m = l + (r - l) / 2;
            long t = (long) m * m;
            if ((long) m * m == x) {
                return m;
            }
            if (t < x) {
                l = m + 1;
            }
            if (t > x) {
                r = m - 1;
            }
        }
        return l;
    }
    0 赞同 0 条回复
  • Cc. 永久会员 2023年9月8日 下午7:32

    下面是代码

    “`java
    int myUpperSqrt(int x){
    int l = 1;
    int r = x;
    while(l<=r){ if(r - l <= 1){ return l * l >= x ? l : r;
    }
    int mid = l + (r-l)/2;
    if (mid*mid < x){ l = mid + 1; }else if (mid*mid > x){
    r = mid;
    }else{
    return mid;
    }
    }
    return 0;
    }

    0 赞同 0 条回复
  • 泡芙 永久会员 2023年8月24日 上午11:54 
    int myUpperSqrt(int x){
    int l = 0;
    int r = x;
    while (l <= r) {
        // r = mid 不会出现死循环，当剩下两个数时，取左边的，即l，所以不影响
        if (l == r) {
            return l;
        }

        int mid = l + (r - l) / 2;
        if ((long)mid * mid > x) {
            r = mid;
        } else if ((long)mid * mid < x) {
            l = mid + 1;
        } else {
            return mid;
        }
    }
}
    0 赞同 0 条回复
  • Thaddeus 永久会员 2023年8月23日 下午4:33
    求上限
    int myUpperSqrt(int x){
  int l = 0;
  int r = x;
  while(l <= r){
    if(r - l <= 1){
      return l * l > x ? l : r; //解有3种情况：1.只剩一个数 2.剩两个数，一个平方x 3.剩两个数，两个平方都>x
    } 
    int mid = l + (r - l) / 2;
    if((long)mid * mid > x){
      r = mid; //只有平方>x的数才可能是解，因此保留
    }else if((long)mid * mid < x){
      l = mid + 1;//平方
    0 赞同 0 条回复
  • 阿尚 普通 2023年8月15日 下午11:53 
    class Solution {
    public int mySqrt(int x) {

        int left = 0, right = x, ans = -1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if((long)mid * mid >= x){//判断条件
                ans = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }

        return ans;
    }
}
    0 赞同 0 条回复
  • 纸飞机 永久会员 2023年8月2日 上午3:10

    “`c++
    int myUpperSqrt(int x){
    //闭区间
    int l = 0 ;
    int r = x ;
    int mid ;
    while (l <= r) { if(r - l <= 1) { if (r * r >= x && l * l < x) { return r; } return l ; 

        }
    mid = l + (r - l) / 2;
    if(x < long(mid*mid))
    {
        r = mid;
    }
    else if (long(mid*mid) < x)
    {
        l = mid + 1;
    }
    else
    {
        return mid;
    }

}

return -1;

    }

    0 赞同 0 条回复
  • CrazyJavaBoy 永久会员 2023年7月23日 下午5:16

    求上限：

    class Solution {
    public int mySqrt(int x) {
       int l = 0;
       int r = x;
       while(l <= r) {
           if(r - l <= 1) {
               return r * r > x ? l : r;
           }
           int mid = l + (r - l) / 2;
           if((long)mid * mid > x) {
               r = mid;
           } else if((long)mid * mid < x) {
               l = mid + 1;
           } else {
               return mid;
           }
       }
       return -1;
    }
}

    求下线：

    class Solution {
    public int mySqrt(int x) {
       int l = 0;
       int r = x;
       while(l <= r) {
           if(r - l <= 1) {
               return r * r > x ? l : r;
           }
           int mid = l + (r - l) / 2;
           if((long)mid * mid > x) {
               r = mid - 1;
           } else if((long)mid * mid < x) {
               l = mid;
           } else {
               return mid;
           }
       }
       return -1;
    }
}
    0 赞同 0 条回复
  • 壁外调查 永久会员 2023年6月23日 下午10:40

    提交
    int myUpperSqrt(int x){
    int l = 0, r = x, ans = -1;
    while (l <= r) {
    int mid = l + (r – l) / 2;
    if ((long) mid * mid < x) {

                    l = mid + 1;
            } else {
                ans = mid;
                r = mid - 1;
            }}
    0 赞同 0 条回复
  • Zn_XiangR 永久会员 2023年6月10日 下午5:11

    提交

    int myUpperSqrt(int x){
     int l  = 0;
     int r = x;
     while (l <= r) {
          if  (l - r <= 1) return l * l > x ? l:r;
          int mid = l + (r - l ) / 2;
          if ((long)mid * mid < x) {
               l = mid + 1;
          } else if (mid * mid > x) {
               r = mid;
          } else {
              return mid;
          }
    }
  return -1;
}
    0 赞同 0 条回复
  • KEV 永久会员 2023年5月27日 下午9:36

    将之前L、R的思想互换一下。在mid*mid > x时，R反而可能是我们需要求的。

    int myUpperSqrt(int x){
    int l=0,r=x;
    while(l<=r){
        if(r-l<=1){
            return r*r > x ? l:r;
        }
        int mid=l+(r-l)/2;
        if((long)mid*mid < x){
            l=mid+1;
        }else if((long)mid*mid > x){
            r=mid;
        }else{
            return mid;
        }
    }
    return -1;
}
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年5月20日 下午5:01

    之前刷的时候没看见这个作业，补交

    int myUpperSqrt(int x){
        int left = 0;
        int right = x;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if((long)mid * mid > x){
                right = mid - 1;
            }else if((long)mid * mid < x){
                left = left + 1;
            }else {
                return mid;
            }
        }
        return left;
}
    0 赞同 0 条回复
  • 路易十二👑 普通 2023年5月9日 上午11:20

    以下是鄙人答案

    function myUpperSqrt(x) {
    let l = 1, r = x, mid = r, cur = -1;
    while (l <= r) {
        mid = Math.floor(l + (r - l) / 2), cur = mid * mid;
        if (cur === x) {
            return mid;
        } else if (r - l <= 1) {
          return l * l > x ? l : r;  
        } else if (cur > x) {
            r = mid;
        } else if (cur < x) {
            l = mid + 1;
        }
    }
    return mid;
};
    0 赞同 0 条回复
  • Violet 永久会员 2023年4月19日 下午12:14

    一

    public int mySqrt(int x) {
        int l = 0, r = x;
        int middle;
        while (l <= r) {
            middle = l + (r - l) / 2;
            if ((long)middle * middle > x) {
                r = middle - 1;
            } else if((long)middle * middle < x){
                l = middle + 1;
            } else {
                return middle;
            }
        }
        return l;
    }
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年4月13日 下午8:58

    #时间复杂度O(logn)
    class Solution:
    def myUpperSqrt(self, x: int) ->int:
    l = 0
    r = x
    while l <= r:
    if r – l <= 1:
    return r if l * l < x else l
    mid = l + (r – l) // 2
    if mid * mid > x:
    r = mid
    elif mid * mid x:
    return mid
    else:
    l = mid + 1
    return -1

    0 赞同 0 条回复
  • 席 永久会员 2023年4月12日 下午4:04 
    //求算术平方根，要求保留的结果为整数，如果是小数则向上取整
public static int mySqrt2(int x){
        int l = 0;
        int r = x;
        while (l <= r) {
            if (r - l <= 1) {    
                return r * r > x ? r : l;   
            }
            int mid = l + ((r - l) >> 1);
            if ((long) (mid * mid) == x) {
                return mid;
            } else if ((long) (mid * mid) > x) {
                if ((long) ((mid-1) * (mid-1))>x){
                    r = mid-1;
                }else{
                    r=mid;
                }

            } else {
                l = mid+1;  
            }
        }
        return -1;
    }
    0 赞同 0 条回复
  • Kuraying_pat 普通 2023年4月12日 上午11:15

    题目只要求取整数，由暴力求解的启发，只要查找到对应的数即可；

    int myUpperSqrt(int x) {
    int l = 1, r = x;
    while (l <= r) {
        int mid = (r + l) / 2;
        if ((r - l) <= 1) return l * l < x ? r : l;
        if ((long)mid * mid > x) r = mid;
        else if ((long)mid * mid < x) l = mid + 1;
        else return mid;
    }
}
void main(void) {
    printf("%d", myUpperSqrt(8));
}
    0 赞同 0 条回复
  • sasuke 普通 2023年4月11日 下午4:11 
    #时间复杂度O(logn) 空间复杂度O(1)
class Solution(object):
    def  myUpperSqrt(num):
        l=0
        r=num
        while l<=r:
            if r-l<=1:
                return r if l*l<num else l
            mid=l+(r-l)//2
            if mid*mid<num:
                l=mid+1
            elif mid*mid==num:
                return mid
            else:
                r=mid
        return -1
    0 赞同 0 条回复
  • 灼华 永久会员 2023年4月9日 下午8:04 
        public static int myUpperSqrt(int x) {
        int l = 0;
        int r = x;
        int mid= l + (r - l) / 2;
        while(l <= r) {//当只剩下两个数的时候，，因为l=mid
            if(r - l <= 1) return l * l >= x ? l : r;
            mid = l + (r - l) / 2;
            if((long)mid*mid > x)r = mid;
            else if((long)mid*mid == x) return mid;
            else l = mid + 1;
        }
        return -1;
    }
    0 赞同 0 条回复
  • Only You!(^-^(^-^)) 永久会员 2023年4月9日 下午7:41 
    /*
     * 二分查找
     * 时间复杂度O(logn) 空间复杂度O(1)*/
    public int myUpperSqrt(int x) {
        int l = 1, r = x;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long)mid * mid < x){
                l = mid + 1;
            }else if ((long)mid * mid > x) {
                r = mid - 1;
            }else return mid;
        }
        return l;
    }
    0 赞同 0 条回复
  • 小趴菜 永久会员 2023年4月8日 下午11:57

    时间复杂度O（logn）
    public int myUpperSqrt(int x) {
    int left = 0;
    int right = x;
    while (left <= right) {
    if(left right){
    return left;
    }
    int mid = left + (right – left) / 2;
    if ((long) mid * mid     x) {
    return mid;
    } else if ((long) mid * mid > x) {
    right = mid;
    }
    else {
    left = mid + 1;
    }
    }
    return -1;
    }

    0 赞同 0 条回复
  • 闲山 普通 2023年4月8日 下午9:55

    时间复杂度O（logn）

    int myUpperSqrt(int x){
        int left =1;
        int right =x;
        while(left<=right){
            if (right-left<=1){
                return right;
            }
       int mid = left + (right-left)/2;
             if (mid*mid>x){
                right=mid;
            }
            else if (mid*mid<x){
                left=mid+1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }
    0 赞同 0 条回复
  • Bryce 普通 2023年4月7日 下午9:25

    go语言，时间复杂度O(logn)。
    使用mid*mid可能会超边界，使用mid>x/mid则要添加x%mid!=0的条件，各有好处吧。
    回头再学习一下其他人的解法。

    func myUpperSqrt(x int) int {
    if x <= 1 {
        return x
    }
    l, r := 0, x
    var mid int

    for l < r {
        mid = l + (r-l)>>1
        if mid == x/mid && x%mid == 0 {
            return mid
        } else if mid > x/mid {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return r
}
    0 赞同 0 条回复
  • 庄重 普通 2023年4月7日 下午4:21 
    // 做个两组测试，不会出现死循环
// 由于‘/’是向下取整，l也等于向下取整的数，没有进行缩小，最后出现死循环
int sort (int x) {

    int l = 0;
    int r = x;

    while(l < r){

        int mid = l + (r-l)/2;
        if(mid*mid > x){
            r = mid;
        }else if(mid*mid == x){
            return mid;
        }else{
            l = mid + 1;
        }
    }
    return l;
}
    0 赞同 0 条回复
  • 是梦终空 永久会员 2023年4月7日 下午12:31

    二分查找，l = r是有意义的,所以while是<=,然后还有l = mid + 1，不+1一直循环了
    时间复杂度 O(logn)

    class Solution {
    public int mySqrt(int x) {
        int res  = -1;
        int l = 0;int r = x;
        while(l <= r){
            int mid = (l+r)/2;
            if((long) mid * mid <= x){
                l = mid + 1;
                res = mid;
            }else if((long) mid * mid > x){
                r= mid-1;
            }
        } 
        return res;
    }
}
    0 赞同 0 条回复
  • 秊 永久会员 2023年4月7日 下午12:21

    和 小肸 想法一样，可以将问题转化为：求一个有序数组中（可重复），与 target 相等的最后一个值的下标，如果没有，返回第一个比 target 大的值的下标

        public int myUpperSqrt(int x){
        if (x == 0) return x;
        int l = 1;
        int r = x;

        while (l < r) {
            int mid = l + (r - l) / 2;
            long mm = (long)mid * mid;
            if (mm > x) {
                r = mid;
            } else if (mm == x) {
                return mid;
            } else {
                l = mm + 1;
            }
        }

        return l;
    }
    0 赞同 0 条回复
  • LicodeCO.LTDao 普通 2023年4月6日 下午11:05

    作业2打卡

    function myUpperSqrt(x: number): number {
  let l = 0;
  let r = x;
  while (l <= r) {
    if (r - l <= 1) {
      return l * l > x ? l : r;
    }
    let mid = l + ((r - l) >> 1);
    if (mid * mid > x) {
      r = mid;
    } else if (mid * mid == x) {
      return mid;
    } else {
      l = mid + 1;
    }
  }
  return -1;
}
    0 赞同 0 条回复
  • 小肸 永久会员 2023年4月5日 下午9:35

    类似于二次查找找得到值就返回数组下标，找不到就返回第一个大于值的元素下标。找上界。
    注意long temp = mid * mid时，mid也必须是long类型，因为mid * mid 可能溢出int型，然后溢出的值赋给了long。但（long）(mid * mid)没有限制，或者赋值语句写成long temp = (long) mid * mid;

    int myUpperSqrt(int x) {
    long left = 0, right = x / 2;
    while (left <= right ) {
        long mid = left + ((right - left) >> 1);
        long temp = mid * mid;
        if (temp < x) {
            left = mid + 1;
        } else if (temp == x) {
            return (int) mid;
       } else {
            right = mid - 1;
       }
       return (int)left;
}
    1 赞同 0 条回复
  • Everglow 永久会员 2023年4月5日 下午7:14 
    int myUpperSqrt(int x) {//评论必须含中文
        int left = 0;
        int right = x;
        while(left < right) {
            int mid = (left + right) >>> 1;
            long midVal = (long) mid * mid;
            if (midVal < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    1 赞同 0 条回复
  • 宁 永久会员 2023年4月5日 下午5:11

    准备好的一个二分模板，注意long
    求上界，那就是第一个平方大于或等于的。

    class Solution {
    public int mySqrt(int x) {
        int l = 0;
        int r = x;
        while(l <= r){
            int m = (r - l) / 2 + l;
            if((long)m * m < x){
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        return l;
    }
}
    0 赞同 2 条回复
  • 菜心 永久会员 2023年4月5日 下午4:41 
    int myUpperSqrt(int x){ //评论必须含中文
        int l = 0;
        int r = x;
        while(l <= r) {
            if(r - l <= 1) {
                return l * l >= x ? l : r;
            }
            int mid = l + (r - l) / 2;
            if((long)mid*mid > x){
                r = mid;
            } else if((long)mid*mid == x) {
                return mid;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
    1 赞同 0 条回复
  • mpweixin用户 普通 2023年4月5日 下午4:09 
     public int mySqrt(int x) {

      int left=0;
      int right=x;


      while(left<=right){
        if(right-left<=1){
          return right*right>x?right:left;
        }
        int mid =left+(right-left)/2;
        if((long)mid*mid<x){
          left=mid;
        }
        else if((long)mid*mid>x){
          right=mid;
        }
        else
        return mid;
      } 
      return 0;
    }
    0 赞同 0 条回复
  • 有去过的人 普通 2023年4月5日 下午3:41

    下面是代码

    int mySqrt(int x){
    int l=0;
    int r=x;
    int mid;
    while(l<=r)
    {
        if((r-l)<=1)
        {
            if(r*r>x)
                return r;
            else
                return l;
        }
       mid=l+(r-l)/2;
       if((long)mid*mid>x)
           r=mid;
       else if((long)mid*mid==x)
           return mid;
       else
            l=mid;
    }
    return -1;
}
    1 赞同 0 条回复
  • C++小将 永久会员 2023年4月5日 下午2:26
    作业二打卡
    int myUpperSqrt(int x) {
    int l = 0, r = x, ans = -1;
    while(l <= r){
        int mid = l + (r - l) / 2;
        if((long long)mid * mid >= x){
            r = mid - 1;
            ans = mid;
        }else{
            l = mid + 1;
        }
    }
    return ans;
}
    1 赞同 0 条回复

# 回答此问题

后才能回答