开平方
二分法,看单调函数走势,注意如何求 mid,以及注意除0 ,溢出
package leetcodemid.二分专题;
/**
* 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
* <p>
* 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
* <p>
* 注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
* <p>
* <p>
* <p>
* 示例 1:
* <p>
* 输入:x = 4
* 输出:2
* 示例 2:
* <p>
* 输入:x = 8
* 输出:2
* 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
* <p>
* <p>
* 提示:
* <p>
* 0 <= x <= 231 - 1
*/
public class MySqrt {
/**
* 二分法,看这个函数的图形 单调函数
* @param x
* @return
*/
public static int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
//
int mid = l + (r - l) / 2;
if ( (long)mid*mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
/**
* 第二种写法
* @param x
* @return
*/
public static int mySqlr2(int x){
//特殊值特殊处理
if(x == 1 || x == 0){
return x;
}
int left = 0;
int right = x;
int mid = 0;
//经典二分—注意等值处理
while(left <= right){
mid = left + (right - left) / 2;
if(mid > x / mid){
right = mid - 1;
}else if(mid < x / mid){
left = mid + 1;
}else{
//相等毫无疑问返回mid
return mid;
}
}
//否则,则一定是right
return right;
}
public static void main(String[] args) {
System.out.println(mySqrt(4));
}
}
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!
版权声明:本文内容来自第三方投稿或授权转载,原文地址:https://blog.51cto.com/u_12550160/4803940,作者:小傻孩丶,版权归原作者所有。本网站转在其作品的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如因作品内容、版权等问题需要同本网站联系,请发邮件至ctyunbbs@chinatelecom.cn沟通。