# Square Root Estimation - Binary Search / Sorted Array

in this code snippet you don’t need to check for 0:
def square_root(n: int) → int:

``````left, right = 0, n
mid = -1
first_smaller_or_equal = -1

while left <= right:
mid = (left + right)//2
if mid**2 == n:
return mid
elif mid**2 < n:
first_smaller_or_equal = mid
left = mid + 1
else:
right = mid - 1

return first_smaller_or_equal
``````

Why binary search when

``````def square_root(n: int) -> int:
return int(n ** .5)
``````

does the trick?

IMO, if we change the feasible function to `i^2 <=n`, the code gets simpler as follow:

``````        if (n == 0) return 0;

int left = 1;
int right = n;
int res = -1;

while(left <= right) {
int mid = left + (right - left) / 2;
if(mid <= n / mid) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}

return res;
``````

def square_root(n: int) → int:
def feasible(val):
return val**2
left, right = 0, n
current_root = -1
while left <= right:
mid = (left + right)//2

``````    current_square = feasible(mid)
if current_square == n:
return mid
elif current_square > n:
right = mid - 1
else:
left = mid + 1
current_root = mid
return current_root
``````

Not really using binary search but instead a math trick in Python:

def square_root(n: int) → int:
if n == 0 or n == 1:
return n

return int(n**0.5)

``````function squareRoot(n) {
if(n===0) return 0
let left = 1
let right = n
let first = 0

while(left<=right){
let mid = Math.floor((left+right)/2)
if(mid**2===n){
return mid
}else if(mid**2<n){
first = mid
left = mid + 1
}else{
right = mid - 1
}
}

return first
}
``````

This is similar to my Java code as well, I’m wondering about flaws here or if this is less efficient than the solution?

``````    public static int squareRoot(int n) {
int left = 0, sqRoot = n, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int exp = mid * mid;
if (exp == n) return mid;
else if (exp < n) {
sqRoot = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return sqRoot;
}
``````

I tested it with these values and they pass:

``````int[] approxSquares = {3, 8, 13, 18, 145, 119};
int[] perfectSquares = {0, 1, 4, 16, 64, 144, 169, 1089};
``````

# no binary search used

def square_root(n: int) → int:
start = 0
while start * start <= n:
start = start + 1
return start - 1

This was my result and I passed all of the testcases.

``````public static int squareRoot(int n) {
// WRITE YOUR BRILLIANT CODE HERE
float halfN = n/2;

float result = halfN * halfN;

if(result < n){
return n;
}

while(result > n){
halfN /= 2;
result = halfN * halfN;
}
halfN = Math.round(halfN);
return (int)halfN;
}
``````
``````def square_root(n: int) -> int:
# WRITE YOUR BRILLIANT CODE HERE
if n == 0: return 0
l, r = 1, n

while l <= r:
mid = (l + r) // 2
if mid * mid == n:
return mid
elif mid * mid > n:
r = mid - 1
else:
l = mid + 1
return r

return 0
``````

This passes all the test cases. Is there a problem with just returning the right-most bound after the `while` loop ends?

This solution may be more elegant:

``````def square_root(n: int) -> int:
# WRITE YOUR BRILLIANT CODE HERE
l, r = 0, n
last_index = -1
while l <= r:
mid = (l + r)//2
if mid*mid <= n:
last_index = mid
l = mid + 1
else:
r = mid - 1

return last_index
``````
1 Like

This is the solution I got as well.

I think it makes more sense mapping (mid*mid) <= n as “true” and finding the righmost “true” in the boolean mapping rather than what the explanation is saying

I recognize the overall goal here is to teach pattern recognition to quickly solve an algorithm, as in this case, recognizing that you can solve it by recycling the binary search solution. However, I wanted to point out you can optimize this solution by recognizing that for n >= 4, the square root will be less than half of n. In this case, we can add an extra check for when n = 1, and allow the logic of the while loop to correctly identify the square root of n = 2 and n = 3 rounds down to 1 when setting right to 1.

Spoiler Solution

``````function squareRoot(n) {
if (n === 0 || n === 1) return n;
let left = 1;
let right = Math.floor(n / 2);
let res = -1;

while (left <= right) {
const mid = left + Math.floor((right - left) / 2);

if (mid**2 === n) {
return mid;
} else if (mid**2 > n) {
res = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}

return res - 1;
}
``````

Clean solution:

`````` public static int squareRoot(int n) {
int l = 1, r = n;
while (l <= r) {
int mid = l + (r - l) / 2;
if (mid == n / mid) return mid;
else if ( mid > n / mid) r = mid - 1;
else l = mid + 1;
}
return r;
}
``````

One more solution:

``````public static int squareRoot(int n) {
int left = 0, right = n, ans = -1;

while (left <= right) {
int mid = left + (right - left) / 2;
if (mid * mid == n) {
return mid;
} else if (mid * mid > n) {
right = mid - 1;
} else {
ans = mid;
left = mid + 1;
}
}

return ans;
}
``````