Square Root Estimation - Binary Search / Sorted Array

Problems
1

https://algo.monster/problems/sqrt

3

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

4

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

5

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

6
  • 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
7

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)<=2eps){
return Math.trunc(mid)
}
if (sq > n) {
right = mid-eps;
}else {
left = mid+eps;
}

}
return result;

}

8

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

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

9

I think the explanation is wrong:

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

10

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

11

think of it as mid^2 <= n

12

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…”?

13

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;
}
2 Likes
14 
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;
}
15

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

16

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
1 Like
17

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.

18

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

19

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

20

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
    int possibleAnswer=-1;
    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
            possibleAnswer=midle;
            start=midle+1;
        }
    }
    return possibleAnswer;
}
21

my JS solution

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

let left = 0
let right = n
let boundary = -1 
let answer = null

while(left <= right){
    answer = (left + right) / 2
    if(answer*answer < n){
        left = answer + 1
        boundary = answer
    } else if(answer * answer > n){
        right = answer - 1
        boundary = answer
    } else if(answer * answer == n || Math.floor(boundary) == Math.floor(answer)){
        return Math.floor(answer)
    } 
}

return Math.floor(answer);

}