69. Sqrt(x)

---

My Solution

The Key Idea for Solving This Coding Question

C++ Code

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

Time Complexity

$O(logx)$
x is the input nonnegative integer.

Space Complexity

$O(1)$

Miscellaneous