### 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:

Input `num` | Output | Explanation |

`4` | `2` | |

`16` | `4` | |

`225` | `15` | |

`5` | `2` | `sqrt(5) = 2.23` rounded to `2` |

### 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)`

.