69. Sqrt(x)

今天我们一起挑战leetcode第69题Sqrt(x)！

题目

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:
Input: x = 4
Output: 2

Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

今天这题要求我们实作一个根号功能，并且不能使用程序语言内建的函式，题目会给我们一个整数，我们要回传此整数开平方根後的结果，并且只需要回传到整数位。

牛顿迭代法

这题我们当然可以用最暴力的解法，用回圈一个个去试有可能的整数，我们知道这样的速度会非常慢。而我们可以透过二分搜寻法，来降低搜寻目标数字的速度。
然而，这题与数学中的牛顿迭代法是有相关的，其中的原理和概念比较偏向数学原理，如果有兴趣可以阅读下列这篇文章。简单来说，牛顿迭代法是在一开始给出一个猜测值，接着不断对这个值进行一些操作（用猜测值与原本题目给的整数做运算），直到求出解答。
https://www.itread01.com/content/1546915711.html

以下是python的程序码

class Solution:
    def mySqrt(self, x: int) -> int:
        guess = 1000  # 猜测值
        while True:
            p = int(guess)
            q = p + 1
            guess = (guess + x / guess) / 2  # 根据牛顿迭代法做出的运算，可以快速接近欲求的数值
            if p**2 <= x and q**2 > x:  # 找到我们要的了！
                break 
        return int(guess)  # 回传整数就好