#!/usr/bin/env python
# coding:utf-8

"""
69. x 的平方根
难度
简单

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
     由于返回类型是整数，小数部分将被舍去。
"""


# ================================================================================
"""
二分查找
"""
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x <= 1:
            return x
        #
        left, right = 0, x/2
        while left <= right:
            mid = (left + right)/2
            s = mid * mid
            if s == x:
                return mid
            elif s < x:
                # left = mid  # !!!!!
                left = mid + 1
            elif s > x:
                # right = mid  # !!!!!
                right = mid - 1
            pass
        return right  # !!!

# ================================================================================
"""
牛顿迭代法
"""
"""
牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method），
它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。
方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。

牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。

另外该方法广泛用于计算机编程中。
"""
"""
根据牛顿迭代的原理，可以得到以下的计算 sqrt(n) 的迭代公式：
    X(n+1)=[X(n)+p/X(n)]/2。
"""
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        """
        牛顿迭代法
        """
        if x <= 1:
            return x
        #
        ret = 1.0 * x/2
        while ret != (ret + x/ret)/2:
            ret = (ret + x/ret)/2
            pass
        return int(ret)
# ================================================================================
# ================================================================================

