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)  # 回傳整數就好