一：題目

解釋：返回x的算數平方根，如果是小數，則舍去小數部分，返回整數即可！

二：算法

①：暴力

從1開始求平方，最后要么直接找到一個值的平方為x，要么發現x在兩個相鄰的數的平方之間

暴力的時間復雜度為O(N)

但是我們從暴力得知，最后返回的一定是left，因為雙指針相遇返回left和right都可以，但是如果發現x是兩個相鄰的數的平方之間，則返回left，因為題目要求向下取整

②：二分

做過了上道題目，此題簡直如魚得水！

我們將數組劃分為兩個部分，左部分值的平方<=x，右部分值的平方>x，本質是因為數組有可能沒有直接平方等于x的值，所以左部分是<=

其次我們的區間的范圍直接從1~x開始即可，因為只要一個數是正整數，則其一定小于其的平方！

所以：

mid*mid <=x 則left=mid? //落入左部分

mid*mid >x 則right=mid-1 //落入右部分

很顯然，我們的求中點的式子必須為：mid = left + (right - left + 1) / 2！

因為，我們說過mid不能落在原地踏步的指針上，此題left=mid，所以不能落在left上，所以我們選擇該式子，當只有兩個元素的時候，mid會落在right指針上

其次循環的條件必定是left<right，避免雙指針相遇再次進入循環，導致原地踏步死循環！

三：代碼

class Solution {
public:int mySqrt(int x) {if (x < 1) return 0;int left = 1, right = x;while (left < right) {long long mid = left + (right - left + 1) / 2;//long long 防溢出if (mid * mid <= x) left = mid;else right = mid - 1;}return left;}
};

解釋：

1：循環條件，left<right

2：求中點式子，mid = left + (right - left + 1) / 2;?

3：返回的是left

4：x可能為0~1之間，所以一開始特判即可