[leetcode in golang]69、x的平方根

按简单程度排：

（居然看见）暴力解：

func mySqrt(x int) int {
    i:=0
    for(!(i*i<=x&&(i+1)*(i+1)>x)){
        i++
    }
    
    return i
}

二分查找
第一次写出来的东西没有二分法的思想

func mySqrt(x int) int {
    i:=0
    j:=(x/2)+1
    for i<j{
        mid:=(i+j)/2
        if mid*mid==x{
            return mid
        }
        if mid*mid<x{
            i++
        }else{
            j--
        }
    }
    return j
}

也难怪测试不通过。
二分法中最重要的中间值mid，通过mid判断舍弃不可能的一边，减少一半的运算内容。
正确做法，注意for循环i=j的边界条件

func mySqrt(x int) int {
    i:=0
    j:=(x/2)+1
    for i<=j{
        mid:=(i+j)/2
        if mid*mid==x{
            return mid
        }
        if mid*mid<x{
            i=mid+1
        }
        if mid*mid>x{
            j=mid-1
        }
    }
    return j
}

牛顿迭代法

有疑问加站长微信联系（非本文作者）