題目

實現 int sqrt(int x) 函數。

計算并返回 x 的平方根，其中 x 是非負整數。

由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。

示例 1:

輸入: 4
輸出: 2

示例 2:

輸入: 8 輸出: 2 說明: 8 的平方根是 2.82842…,
由于返回類型是整數，小數部分將被舍去。

二分法

我們要找的是滿足 ans * ans <= x 中ans的最大值。
以0位左邊界，x為右邊界開始折半查找滿足情況的數。
由于題目要求的是向下取整的數，而最后不滿足while條件退出時的start已經在原有的基礎上+1了，所以需要進行-1操作。

class Solution {
public:int mySqrt(int x) {int start = 0;int end = x;//int ans = 0;int mid = (start + end) / 2;while(start <= end){mid = (start + end) / 2;if((long long)mid*mid == x) return mid;else if((long long)mid*mid > x){end = mid - 1;}else {start = mid + 1;}}return start - 1;}
};

牛頓迭代法

用一階泰勒展式（即在當前點的切線）代替原曲線，求直線與 x 軸的交點，重復這個過程直到收斂。
迭代公式為：
x =0.5( x + a/x)

class Solution {
public:int mySqrt(int x) {double cur = 1;double pre = 1;while(true){pre = cur;cur = (cur + x / cur) / 2;if(abs(pre - cur) < 1e-6)return (int)cur;}}
};