Bisection Search: BEHIND THE SCENES!

BISECTION SEARCH

Hi! Welcome to this section on Bisection search .

This is an amazing algorithm (I loved it when I first saw it in the course), it can find a value much faster than a simple approach. In these diagrams you can experience how this algorithm works, and how each step is determined by an "error" or epsilon.

I've used the same code from the lecture, but in this case, we find the square root of 9 with an epsilon 0.08, and I've added some print statement to help us see what's going on on each step. With a low starting point from 0.0 and a high point of 9, we start our algorithm.... This is what we see on the shell:

Python's Shell:

First, the algorithm asks if the answer found (the middle point of the search space) is close enough to the answer we are looking for (if the answer squared is within epsilon of the value for which we are calculating the square root) below you will find a visual explanation of this process

(Check diagrams below to follow this explanation graphically)

We start with a search space from 0.0 up to 9. We know that the square root of 9 is 3, so we have an idea of where the algorithm will find the answer (this will help us through the explanation).
On each step, the algorithm determines if the answer is close enough to the answer we are looking for, within a margin of error (epsilon). If we square the answer (the middle point of the search space) and we get that its either larger or smaller than our initial number 9, it may still be the answer we are looking for if that difference is smaller than epsilon. (For example, if we say epsilon is 0.5, and we want the square root of 9, if our answer squared gives us 8.6 or 9.4, those are "acceptable" answers because they are within that margin of error we've set, this is the meaning of epsilon)

If it's not within epsilon, it means it's not precise enough, and we have to reduce our search space even further.

But how do we determine where to keep looking? We can reduce our search space BY HALF on each step!

We can reduce our search space BY HALF! on each step by noting if the answer squared is too small or too large to be the right answer.
- If our answer squared is too small, the algorithm will discard the half of the search space that contains numbers smaller than our answer, and our new search space will be the other half that contains numbers larger than our previous answer. Our new Low will be the previous answer (the middle point of the previous search space) and our High point will remain the same.
- On the contrary, if our answer squared is too large to be the right answer, the algorithm will discard the HALF of the search space that contains numbers Larger than our previous answer. Our new High point will be the previous answer (the middle point of the previous search space) and our Low point will remain the same.

These steps will repeat until the algorithm finds an answer that, squared, is close enough to the initial number for which we are trying to calculate the square root. (in this case 9)