Also known as **bisection method**; **binary search** or **dichotomy method**.
**Method**
Suppose that $f:[a,b] \to \mathbb{R}$ is [[Continuous Real Function|continuous]] with $f(a)<0<f(b)$. We want to find a point $c\in (a,b)$ such that $f(c)=0$. We define, using induction, a sequence of decreasing intervals on which $f$ changes sign, to 'narrow down' onto the point $c$. The iteration task is defined below:
Let $a_{1}=a$, $b_{1}=b$. Suppose $f(a_{n}) <0$ and $f(b_{n})>0$. Let $t_{n}=\frac{a_{n}+b_{n}}{2}$ and
1. if $f(t_{n})<0$ then let $a_{n+1}=t_{n}$ and $b_{n+1}=b_{n}$;
2. if $f(t_{n})>0$ then let $a_{n+1}=a_{n}$ and $b_{n+1}=b_{n}$;
3. if $f(t_{n})=0$ then we have found the required point $c=t_{n}$.
Note that unless we are are in case (3), we have $f(a_{n+1})<0<f(b_{n+1})$.
As shown here [[Intermediate Value Theorem (IVT)]], if case (3) never occurs then $a_{n}\to \alpha \leftarrow b_{n}$ as $n \to \infty$ such that $f(\alpha)=0$.
**Python Implementation**
Interval halving gives a way of finding roots of equations numerically as shown below:
```run-python
def root_estimate(f,a,b,TOL,NMAX):
# inputs: function f; endpoints a, b; tolerance TOL; maximum iterations
# conditions: a<b & f(a)< 0 < f(b)
N = 1
while N <= NMAX:
t = (a+b)/2
if f(t) == 0 or (b-a)/2 < TOL: return t
if t < 0: a = t
else: b = t
N += 1
return("Max number of steps exceeded")
# test
def f(x): return x**2
root = root_estimate(f,-1,1,0.00001,1000)
print(root)
```