Your task is to implement the bisection method for finding a solution $x$ of the equation $$ f(x)=0. $$ Here $f$ is a real-valued function of a single real variable $x$ and the solution of the above equation is called a root of $f$.
Many nonlinear algebraic equations, such as $x = 1 + \cos x$ do not admit a closed form solution. But a numerical method can find an approximate solution by finding the root of $f(x) = x - 1 - \cos x.$
Bisection is a numerical method to solve for a root of a function $f(x)$ of a single real variable $x$. Here is its description:
The Bisection method
Halve the interval and set the midpoint $m = (a+b)/2$.
At the $n$th step, the initial interval $[a,b]$ has been halved $n$ times and we know that $f(x)$ must have a root inside a small subinterval of length $2^{-n}(b-a)$. Since the root is contained in this subinterval, $\text{error}\le 2^{-n}(b-a).$
Hence we may stop the subdivisions when $n$ is such that $$ 2^{-n}(b-a) \le \epsilon. $$ for some user specified error tolerance $\epsilon$, and take the midpoint $m$ as the root.
Hints and suggestions
Write down your steps as a precise algorithm (before you code) in terms of for/while, if, else, etc. Use this to map out how you will write your code.
Write a first version of the code and make sure it is working on a test problem. Your code should be in the form of a function
def bisection(f, a, b, eps, niters):
# Code goes here.
where f, a, b, and eps represent $f$, $a$, $b$ and $\epsilon$ in the above description, and niters is the maximal number of iterations, which in this case is the maximal number of subdivisions of the initial interval you will make (whether or not the eps tolerance is met).
Test your bisection code on the function $f(x)$ whose roots you know, say $f(x) = \cos(x)$. Once you know your current code is working correctly, proceed to the next step. If you jump this step, beware that "premature optimization is the root of all evil," according to Donald Knuth.