If OpenAI can get away with it.....

Hello and welcome back brave human being,

Before we delve into the problem, I want to say, you deserve better. You deserve someone who would stick to their promise of sending a problem and solution to this challenge and I have not met the expectations.

The truth is; that I got burned out from doing these emails, especially the animations.

But as humans, we are visual creatures, and these visualizations help me solve problems I’m sure you get value out of it as well. ( If not PLEASE reply to this email and let me know!! )

Day 18: 69. Sqrt(x)

Given a non-negative integer x, return the square root of x, without using built-in functions.

You might be thinking, what does this problem have to do with binary search?

And my brave human being. It has everything to do with it. (If you need a refresher on this pattern)

Let’s dive in 🤿 …

The first thing would be, how would you solve this linearly?

We would iterate from 1 to X and for each iteration we would ask, is this the square root?

How could we do this faster? 🚄 

With binary search!

Let’s define our variables

Now let’s start thinking, what would be our stopping condition?

Of course, when middle * middle == X. Have we considered the square root of 8? It is 2.82842 therefore we must return 2.

To catch that case, we’ll add to our stopping condition:

((middle* middle<x )&& (x<(middle+1)* (middle+1 ))

That way we’ll catch all the cases where the square root has a decimal number.

Here is an example…

Final Solution:

See you next Tuesday for a problem with its solution,

Denisse 🥰