69.x的平方根

二分查找

思路

• 满足k^2<=x的最大k值，使用二分查找
• 注意边界问题

代码

/**
     * 1ms 二分查找
     
     *复杂度 O(logx)  O(1)
     * @param x
     * @return
     */
    public int mySqrt(int x){
        int start=0,end=x,ans=-1;
        while(start<=end){
            int mid=(start+end)/2;
            if((long)mid*mid<=x){
                ans=mid;
                start=mid+1;
            }
            else{
                end=mid-1;
            }
        }
        return  ans;
    }

牛顿迭代法 袖珍计算器

官方详解

69.x的平方根