---
# System prepended metadata

title: '[69. Sqrt(x)](https://leetcode.com/problems/sqrtx/)'
tags: [leetcode]

---

---
tags: leetcode
---

# [69. Sqrt(x)](https://leetcode.com/problems/sqrtx/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code
```cpp=
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
<!--
# Test Cases
```
4
```
```
8
```
```
9
```
```
11
```
```
77
```
```
99
```
```
2147395599
```
```
2147483647
```
```
0
```
```
1
```
```
2
```
```
3
```
-->