Python code, Recursive Binary Search, plus a Newton method


  • 0
    W
    class Solution(object):
        def mySqrt(self, x):
            """
            :type x: int
            :rtype: int
            """
            return self.sqx(x,1,x)
        def sqx(self,x,s,e):
            if s>e:
                return e
            m=(s+e)/2
            if x/m==m:
                return m
            elif x/m<m:
                return self.sqx(x,s,m-1)
            else:
                return self.sqx(x,m+1,e)
    

    Newton method-for almost all equation numeric solution

    class Solution:
        # @param x, an integer
        # @return an integer
        def sqrt(self, x):
            epsilon=1.0e-6
            a=1.0
            if x==0:
                return 0
            elif x==1:
                return 1
            else:
                while abs(a**2-x)>epsilon:
                    a=0.5*(a+x/a)
            return int(a)

  • 0

    Hey, I am kinda confused about why did you do a=0.5*(a+x/a)? I thought we should take the derivative in Newton's method?


  • 0
    W

    For x^2=a. The Newton method solve y-y0=y'(x-x0), where y0=x0^2-a and y'=2x0
    so y-x0^2+a=2x0(x-x0), where y=0, so x=1/2(x0+a/x0)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.