Square Root Estimation - Binary Search / Sorted Array

Problems
22

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
23

Why binary search when

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

does the trick?

24

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;
25

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
26

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)

27 
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
}
28

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};
29

no binary search used

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

30

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;
    }
31 
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?

32

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
2 Likes
33

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

34

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;
}
35

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;
    }
36

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;
}
37

what about negative number, the question does not specify +ve or -ve number. For negative number the solution will not work.( left, right = 0, abs(-8)) might work