LeetCode 69. x 的平方根

• 解题思路
• C++代码

二分法（left, middle, right），以 left > right 为终止条件
考虑特殊情况：left == right的时候也进while循环，此时middle*middle == x（或由于小数原因middle*middle <= x），先用ans存下来结果，下一次进入循环已不满足条件。

class Solution {
public:
    int mySqrt(int x) 
    {
        int left = 0, right = x, ans=-1;
        while (left <= right)
        {
            int middle = (left+ right)/2;
            if ((long long)middle*middle <= x)
            {
                ans = middle;//为了middle*middle==x，直接跳出循环的情况
                left = middle + 1;
            }

            else 
            {
                right = middle - 1;
            }
       
        }
        return ans;
    }
};

原本采用的两种方法：暴力法，以及未采用left > right 这一判断条件的二分法