Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explained the algorithm to Find Cube root using Binary Search along with Time and Space Complexity analysis.

Table of contents:

- Introduction
- Finding cube root using Binary Search
- Perfect Cube
- Cube root with precision

- Time and Space Complexity

Pre-requisites:

## Introduction

When someone needs to find the cube of a number, then they can just multiply that number by itself three times, and alas! They have the answer. But, when one needs to go in the other direction (finding cube-root), theirs no direct formula to find this number and, because of this it is required to search this number throughout the space of [1, N].

### A little stroll to Linear Search

If you desire, you can skip this and goto the solution

So, I was curious, why not Linear Search? I mean, it's âˆ›N. maybe a mathematician would know by one look which one is smaller or greater âˆ›N or `log`

._{2}N

Well in my case, I went and took the `log`

of a bunch of numbers and then compared them together and got the following output.

```
from math import ceil, log
for i in range(1, 30, 2):
print("{} - {} | {} - {}".format(
i,
ceil(log(i**3, 2)),
i+1,
ceil(log((i+1)**3, 2))
)
)
```

1 - 0 | 2 - 3 3 - 5 | 4 - 6 5 - 7 | 6 - 8 7 - 9 | 8 - 9 9 - 10 | 10 - 10 11 - 11 | 12 - 11 13 - 12 | 14 - 12 15 - 12 | 16 - 12 17 - 13 | 18 - 13 19 - 13 | 20 - 13 21 - 14 | 22 - 14 23 - 14 | 24 - 14 25 - 14 | 26 - 15 27 - 15 | 28 - 15 29 - 15 | 30 - 15

Conclusion:

As you go further, log starts to become smaller, therefore,

`log`

<_{2}N`âˆ›N`

. So, binary search would be better than Linear.

Well, back to the topic...

## Finding cube root using Binary Search

### Perfect Cube

If we have to find cube root for a perfect cube, then we can just apply binary search directly on the space of [1, N], and return `x`

where `x`

equals to `x`

.^{3}

This should look something like the following,

```
1 def perfect_cube_root(N):
2 start = 1
3 end = N
4 mid = (start + end) // 2
5
6 while mid != start and mid**3 != N:
7 if mid**3 > N:
8 end = mid
9 else:
10 start = mid
11 mid = (start + end) // 2
12 return mid
```

The `(mid != start) and`

condition, in the while loop, help to return a smaller value in case the loop doesn't find a perfect cube root. And without this condition, the loop will run infinitely.

So, for example,

If we do `perfect_cube_root(9)`

, since `9`

comes between two perfect cubes `8`

and `27`

because of this, the above loop will return `2`

, which is a cube-root of `8`

.

Why write this function this way?

Well, we're going to use this in the next `cube_root`

with precision function.

## Cube root with precision

Now to find decimal values of a cube root, we can first search for a smaller result using `perfect_cube_root(N)`

and, if it returns a perfect cube root, then return it or proceed to search for precision.

The idea here is to find a value in decimal which will be a perfect cube root or a nearest smaller value.

In other words, we will search between `.0`

and `.9`

, a perfect match or nearest smaller value, and then decrease the power in the case of `.0`

and `.9`

, another search will happen in-between `.00`

and `.09`

.

And while the above search happens, we should keep adding the found values to the result with increasing precision.

Code for the above idea should look like the following one:

```
1 def cube_root(N, precision=5):
2 P = lambda a, b: a * 10 ** (-b)
3 result = perfect_cube_root(N)
4 if result**3 == N:
5 return result
6
7 for i in range(1, precision + 1):
8 start = 0
9 end = 9
10 mid = (start + end) // 2
11
12 cube = lambda: (result + P(mid, i))**3
13
14 while start != mid:
15 if cube() > N:
16 end = mid
17 elif cube() < N:
18 start = mid
19 elif cube() == N:
20 return result + P(mid, i)
21
22 mid = (start + end) // 2
23
24 result += P(mid, i)
25
26 return round(result, precision)
```

Let us look at an example,

If we run `cube_root(16.003008)`

then it should return `2.52`

.

At first, the `cube_root`

will call `perfect_cube_root`

, and surely it will get the `2`

in return.

Now at `line 7`

we start for-loop for a range of [1, precision + 1] and initialize `start`

, `end`

and `mid`

as 0, 9 and 4.

Notice, `start`

, `end`

, and `mid`

are not decimals reason for that is just that I did not want to deal with float numbers. Calculating `mid`

with float values was a mess and, this approach makes it easier to capture a smaller value if it did not find any value, to form a result for perfect cube root.

Anyway, since `i = 1`

therefore here we're dealing with `10`

precision, means we're searching for perfect or small in between ^{-1}`2.0`

and `2.9`

, at this point when loop will take `start`

and `mid`

at `5`

, `start != mid`

will break the loop and will proceed for `10`

.^{-2}

Hence, it will start searching between `2.50`

and `2.59`

, in this the loop will find `2.52`

as a perfect match and, `line 20`

will execute, which will add `0.02 ( P(mid, i) )`

to `result`

and return it.

## Time and Space Complexity

### Time Complexity:

At first, we're performing purely a binary search which should take **O(logN)** time,

then after this, we perform binary search on space of [0, 9], for **P** times,

which will total to, **Plog(10)**

that is, **4P**.

therefore,

Time Complexity =

O(logN + P)

### Space Complexity:

The function itself takes one *Number* and creates a constant number of variables which use a constant number of space,

therefore,

- Space Complexity =
**O(1)**

With this article at OpenGenus, you must have the complete idea of Finding cube root using Binary Search.