求X的平方根
package com.mtons.mblog.leetcode;
/**
* 求X的平方根
*
*/
class Solution {
/**
* 二分法
* @param x
* @return
*/
public int mySqrt(int x) {
//返回结果只要整数，小于1的平方根都是0.多，舍弃后为0
if (x==0 || x==1)
{
return x;
}
int left=1;
int high=x;
int mid=0;
while (left<=high)
{
mid=left+((high-left)>>1);
//这里不要用平方积，当mid过大会越界，所以用除更好
if (mid==x/mid)
{
return mid;
}else if (mid<x/mid)
{
left=mid+1;
}else {
high=mid-1;
}
}
return high;
}
/**
* 数学公式
* @param x
* @return
*/
public int mySqrt1(int x) {
if (x < 2)
return x;
int curr = (int) Math.exp(0.5 * Math.log(x)) + 1;//注意判断条件应该是取值+1的平方和x对比
return (long) curr * curr > x ? curr - 1 : curr;//curr的平方为方便特殊取值应该用long
}
/**
* 牛顿迭代
* /av42180634/p1
* @param x
* @return
*/
public int mySqrt2(int x) {
long n = x;
while (n * n > x) {
n = (n + x / n) / 2;
}
return (int) n;
}
public static void main(String[] args) {
// default impl. delegates to StrictMath
// Note that hardware sqrt instructions
// frequently can be directly used by JITs
// and should be much faster than doing
// in software.
//public static native double sqrt(double a);
Math.sqrt(2);
Solution solution = new Solution();
System.out.println(solution.mySqrt2(16));
}
}