# Solving Algorithmic Problems: Square Root of an Integer

This post is part of a series on how to solve algorithmic problems. From my personal experience, I found that most of the resources were just detailing solutions. Yet, it was not very common to actually understand the underlying line of thought allowing to reach an efficient solution. Thereby, this is the goal of this series: describing potential processes of reflection to solve problems from scratch.

### Problem

`Implement `sqrt(int a).``
`If `a` is not a perfect square, return `floor(sqrt(a)).``
`Example:`
``Input: 4Output: 2``
``Input: 11Output: 3``

Category: Binary search

### Solving Process

#### Binary Search

The easiest solution would be to iterate from 1 to `a` and check the square value which results in a linear time complexity.

How to improve the complexity? Using a binary search with an O(log(n)) complexity. Bear in mind, every algorithm which removes half of the potential result during each iteration has an logarithmic complexity.

In pseudo-code:

`int f(a) {  low = 1  high = a`
`  while low <= high {    mid = (high + low) / 2    current = mid * mid`
`    if current == a return mid    else if current < a      low = mid + 1    else if current > a      high = mid - 1    }`
`  return high // Because we need the floor value of sqrt}`

As you can see, the algorithm is pretty straightforward. Yet, there is one thing we must take care of as we are working with integer: making sure to not create an integer overflow.

An integer overflow occurs with an operation that results in a value outside of its own range. In Java, as an integer is encoded with 4 bytes, it goes from -2³¹ (-2147483648) to 2³¹-1 (2147483647).

Let’s imagine we would have implemented the previous algorithm using an `int mid`. In the case where `a` equals to Integer.MAX_VALUE, it will trigger an integer overflow during the first iteration resulting in having `mid` equals to -1073741824 (which is as you can imagine not what we expected).

Let’s implement a correct solution using long values:

In both return cases, it is safe to cast the long value into an int.

The algorithm complexity is O(log n) in time and O(1) in space (which by the way would not have been the case with a recursive implementation).