Problem

We need to calculate the square root of a provided integer number num without using built-in functions. The result should be rounded down in case it is not a whole number.

Examples:

Solution

fn sqrt(num: i32) -> i32 {
    assert!(num >= 0);

    let mut left = 0;
    let mut right = num;
    while left < right {
        let mid = (left + right + 1) / 2;
        if mid * mid > num {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    right
}

Explanation

The first idea that comes to mind could be a simple brute force like:

fn sqrt(num: i32) -> i32 {
    let mut sqrt = 1;
    while sqrt * sqrt <= num {
        sqrt += 1;
    }
    sqrt - 1
}

It would work but, obviously, in terms of run-time complexity, it would not be ideal. So, instead of iterating over all numbers, we could improve the solution using Binary Search. The idea is to divide the interval of numbers by 2 to get the middle number mid and then continue the search within either the left or the right half of the interval, repeating the exercise while left < right.

Complexity

The time complexity of this solution is O(lg n) (where n is the input number num). The auxiliary space complexity is O(1).

---

Rust Playground with this code