# Question

Formatted question description: https://leetcode.ca/all/69.html

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

# Algorithm

Binary search method to find square root.

# Code

• 
public class Sqrt_x {

public class Solution {

// @memorize: divide and conquer, in fact it's a binary search. compare with pow() question
public int mySqrt(int x) {
// @note: x < 0, then return Imaginary number?
// proof: sqrt(x) <= x/2, then, x <= x^2/4, then, x^2 - 4x >= 0, then x>=4

if (x < 0) {
return -1;
}

if (x == 0 || x == 1) {
return x;
}

int low = 1; // lowBoundary
int up = x; // upBoundary
int mid = -1;
while (low <= up) {
mid = low + (up - low) / 2;

// if (mid * mid == x) // @note: overflow
if (mid <= x / mid && (mid + 1) > x / (mid + 1)) { // eg: 2^2 <=5, 3^2 > 5
return mid;
} else if (mid < x / mid) {
low = mid + 1;
} else {
up = mid - 1;
}
}

return mid;
}
}

}

############

class Solution {
public int mySqrt(int x) {
int left = 0, right = x;
while (left < right) {
int mid = (left + right + 1) >>> 1;
if (mid <= x / mid) {
// mid*mid <= x
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}

• // OJ: https://leetcode.com/problems/sqrtx/
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
int mySqrt(int x) {
long i = 0;
while (i * i <= x) ++i;
return i - 1;
}
};

• class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x
while left < right:
mid = (left + right + 1) >> 1
# mid*mid <= x
if mid <= x // mid:
left = mid
else:
right = mid - 1
return left

############

class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
lo = 0
hi = x
while lo <= hi:
mid = (hi + lo) // 2
v = mid * mid
if v < x:
lo = mid + 1
elif v > x:
hi = mid - 1
else:
return mid
return hi


• func mySqrt(x int) int {
left, right := 0, x
for left < right {
mid := left + (right-left+1)>>1
if mid <= x/mid {
left = mid
} else {
right = mid - 1
}
}
return left
}

• /**
* @param {number} x
* @return {number}
*/
var mySqrt = function (x) {
let left = 0;
let right = x;
while (left < right) {
const mid = (left + right + 1) >>> 1;
if (mid <= x / mid) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
};


• public class Solution {
public int MySqrt(int x) {
int left = 0, right = x;
while (left < right)
{
int mid = left + right + 1 >> 1;
if (mid <= x / mid)
{
left = mid;
}
else
{
right = mid - 1;
}
}
return left;
}
}

• impl Solution {
pub fn my_sqrt(x: i32) -> i32 {
if x < 2 {
return x;
}
let mut l = 1;
let mut r = x / 2;
while l < r {
let mid = (l + r + 1) >> 1;
if x / mid < mid {
r = mid - 1
} else {
l = mid;
}
}
l
}
}