---
tags: leetcode
---

# [69. Sqrt(x)](https://leetcode.com/problems/sqrtx/)
---
# 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
<!--
# Test Cases

4

8

9

11

77

99

2147395599

2147483647

0

1

2

3

-->