0069 Sqrtx

• Simple
• C++

问题概述

解题思路

class Solution 
{
public:
    int mySqrt(int x) 
    {
        if (x == 0 || x == 1) { return x; }

        long int n = 1;
        while (n * n <= x) { n++; }
        return n - 1;
    }
};

class Solution
{
public:
    int mySqrt(int x)
    {
        if (x == 0 || x == 1) { return x; }
        long int left = 0;
        long int right = x;

        while (left <= right)
        {
            long int mid = left + (right - left) / 2;
            if (mid * mid == x) { return mid; }
            else if (mid * mid < x) { left = mid + 1; }
            else { right = mid - 1; }
        }
        return std::min(left, right);
    }
};