Bisection

You will write the bisection method. The program tests for a sign change, halves an interval again and again, and counts how many halvings a given accuracy needs.

The idea. If $f$ is continuous and $f(a)$ and $f(b)$ have opposite signs, a root lies between $a$ and $b$. Replace the interval by the half where the sign still changes. After $n$ halvings the interval has length $\dfrac{b - a}{2^n}$.

Your tasks.

1. Finish sign_change(f, a, b). Return True when f(a) and f(b) have opposite signs.
2. Finish bisect(f, a, b, steps). Halve the interval steps times, keeping the half with the sign change, and return the midpoint of the final interval.
3. Finish steps_needed(width, tol). Return the smallest whole number n with width / 2 ** n < tol.