Leetcode Study Day 12

Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
 

Constraints:

0 <= x <= 231 - 1

My solution

My solution is intuitive and simple, but it costs O(n) time complexity.

Once a number’s square is larger than x, we return the previous number.

class Solution {
public:
    int mySqrt(int x) {
        long i = 0;
        while (true){
            long j = i + 1;
            if (i * i <= x && j * j > x)
                return i;
            else 
                i ++;
        }
        return -1;
    }
};

Binary Search

Then I saw a solution that using binary search to solve it. It costs O(logn) time complexity.
In this solution, we find the mid number between first (which is initiated as 1) and last (which is initiated as x). If the mid number is equal to x / mid, we return mid. If the mid number is larger than x / mid, we set last as mid - 1. If the mid number is smaller than x / mid, we set first as mid + 1.

Finally, if the first is larger than the last, we return last.

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0)
            return 0;
        int first = 1, last = x;
        while (first <= last){
            int mid = (first+ (last - first)/2);
            if (mid == x / mid)
                return mid;
            else if (mid >= x / mid)
                last = mid - 1;
            else first = mid + 1;
        }
        return last;

    }
};