69.sqrt-x.cpp

/*
 * @lc app=leetcode id=69 lang=cpp
 *
 * [69] Sqrt(x)
 *
 * https://leetcode.com/problems/sqrtx/description/
 *
 * algorithms
 * Easy (30.72%)
 * Total Accepted:    333.5K
 * Total Submissions: 1.1M
 * Testcase Example:  '4'
 *
 * Implement int sqrt(int x).
 *
 * Compute and return the square root of x, where x is guaranteed to be a
 * non-negative integer.
 *
 * Since the return type is an integer, the decimal digits are truncated and
 * only the integer part of the result is returned.
 *
 * Example 1:
 *
 *
 * Input: 4
 * Output: 2
 *
 *
 * Example 2:
 *
 *
 * Input: 8
 * Output: 2
 * Explanation: The square root of 8 is 2.82842..., and since
 * the decimal part is truncated, 2 is returned.
 *
 *
 */
class Solution
{
  public:
    int mySqrt(int x)
    {
        int left = 0;
        int right = x;
        double target = x;
        while (left + 1 < right)
        {
            double mid = (left + right) / 2;
            if (mid * mid == target)
                return mid;
            else if (mid * mid > target)
                right = mid;
            else
                left = mid;
        }
        if ((double)right * (double)right == (double)x)
            return right;
        return left;
    }
};