求X的平方根

短命女 2023-03-13 05:12 10阅读 0赞

求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
        }
    
        /** * 牛顿迭代 * https://b23.tv/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
            // Math.sqrt in software.
            //public static native double sqrt(double a);
            Math.sqrt(2);
            Solution solution = new Solution();
            System.out.println(solution.mySqrt2(16));
        }
    }