# Square Root Estimation - Binary Search / Sorted Array

wrong solution. Doesn’t take care of the overflow like (left+right) and (mid * mid)

The overflow of left + right is taken care of by left + (right - right) / 2;
As of mid * mid, I think you r right

This condition is not explained.
`mid <= n / mid`

• If mid is a square root of n then mid == n / mid. For e.g. let’s say n = 9 and mid is 3 then 3 = 9/3.
• if mid is less then the n then also we want to save that result. e.g. let’s say n = 8 and mid is 2 the 2 < 8/2

function squareRoot(n) {
let result = 0;
if (n<0) return 0;
let left = 0;
let right = n;
let eps = 0.01;
while (left <=right){
let mid = left + ((right-left)/2);
let sq = midmid;
if (Math.abs(sq-n)<=2
eps){
return Math.trunc(mid)
}
if (sq > n) {
right = mid-eps;
}else {
left = mid+eps;
}

``````}
return result;
``````

}

for overflow…just always add left …this has been the easiest to remember for me:

let mid = left + Math.floor((right - left)/2);

I think the explanation is wrong:

arr[i] ^ 2 = n
should be:
arr[i] ^ 2 <= n

I’m having a hard time how you come to the conclusion of n / mid?

think of it as mid^2 <= n

In the first line under the heading ‘explanation’ -
shouldn’t it be “…boundary of elements < n and elements >= 0…” as opposed to “…boundary of elements < n and elements >= n…”?

This should been the code.

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

mid * mid overflow can be easily fixed with an optimization for the upper bound: n/2.

Simpler solution imo

``````def square_root(n: int) -> int:
l, r = 0, n

square = -1

while l <= r:

m = (l + r) // 2

if n >= m*m:
square = m
l = m + 1
else:
r = m - 1

return square
``````

I agree @Abdullah. That’s also what I wrote. If there is something wrong with this approach I’d be interested in understanding why but otherwise this is simpler and passes all the tests.

depending on the language, e.g. python3’s int has no limit

hi, there are many ways to do binary search for different problems. we sticked to the template in the solution

This is my solution for square root estimation

``````    //corner case
if(n==0)
{
return 0;
}
// WRITE YOUR BRILLIANT CODE HERE
int square=n/2;
int start=1;
int end=n;
int midle=-1;
// we need to store our possible answer
while (start<=end)
{
//prevent overflow
midle=end+(start-end)/2;
// we found the square root
if(midle*midle==n)
{
return midle;
}else if(midle*midle>n)
{
end=midle-1;
}else{
// we found a possible answer
start=midle+1;
}
}
}
``````

my JS solution

function squareRoot(n) {
if(n == 1){
return 1
}

``````let left = 0
let right = n
let boundary = -1

while(left <= right){
answer = (left + right) / 2