Algorithm

Bisection method Steps (Rule)
Step-1:	Find points `a` and `b` such that `a < b` and `f(a) * f(b) < 0`.
Step-2:	Take the interval `[a, b]` and find next value `x_0 = (a+b)/2`
Step-3:	If `f(x_0) = 0` then `x_0` is an exact root, else if `f(a) * f(x_0) < 0` then `b = x_0`, else if `f(x_0) * f(b) < 0` then `a = x_0`.
Step-4:	Repeat steps 2 & 3 until `f(x_i) = 0` or `|f(x_i)| <= "Accuracy"`

---

Example-1
1. Find a root of an equation `f(x)=x^3-x-1` using Bisection method

Solution:
Here `x^3-x-1=0`

Let `f(x) = x^3-x-1`

Here

`x`	0	1	2
`f(x)`	-1	-1	5

`1^(st)` iteration :

Here `f(1) = -1 < 0` and `f(2) = 5 > 0`

`:.` Now, Root lies between `1` and `2`

`x_0 = (1 + 2)/2 = 1.5`

`f(x_0) = f(1.5) = 0.875 > 0`


`2^(nd)` iteration :

Here `f(1) = -1 < 0` and `f(1.5) = 0.875 > 0`

`:.` Now, Root lies between `1` and `1.5`

`x_1 = (1 + 1.5)/2 = 1.25`

`f(x_1) = f(1.25) = -0.29688 < 0`


`3^(rd)` iteration :

Here `f(1.25) = -0.29688 < 0` and `f(1.5) = 0.875 > 0`

`:.` Now, Root lies between `1.25` and `1.5`

`x_2 = (1.25 + 1.5)/2 = 1.375`

`f(x_2) = f(1.375) = 0.22461 > 0`


`4^(th)` iteration :

Here `f(1.25) = -0.29688 < 0` and `f(1.375) = 0.22461 > 0`

`:.` Now, Root lies between `1.25` and `1.375`

`x_3 = (1.25 + 1.375)/2 = 1.3125`

`f(x_3) = f(1.3125) = -0.05151 < 0`


`5^(th)` iteration :

Here `f(1.3125) = -0.05151 < 0` and `f(1.375) = 0.22461 > 0`

`:.` Now, Root lies between `1.3125` and `1.375`

`x_4 = (1.3125 + 1.375)/2 = 1.34375`

`f(x_4) = f(1.34375) = 0.08261 > 0`


`6^(th)` iteration :

Here `f(1.3125) = -0.05151 < 0` and `f(1.34375) = 0.08261 > 0`

`:.` Now, Root lies between `1.3125` and `1.34375`

`x_5 = (1.3125 + 1.34375)/2 = 1.32812`

`f(x_5) = f(1.32812) = 0.01458 > 0`


`7^(th)` iteration :

Here `f(1.3125) = -0.05151 < 0` and `f(1.32812) = 0.01458 > 0`

`:.` Now, Root lies between `1.3125` and `1.32812`

`x_6 = (1.3125 + 1.32812)/2 = 1.32031`

`f(x_6) = f(1.32031) = -0.01871 < 0`


`8^(th)` iteration :

Here `f(1.32031) = -0.01871 < 0` and `f(1.32812) = 0.01458 > 0`

`:.` Now, Root lies between `1.32031` and `1.32812`

`x_7 = (1.32031 + 1.32812)/2 = 1.32422`

`f(x_7) = f(1.32422) = -0.00213 < 0`


`9^(th)` iteration :

Here `f(1.32422) = -0.00213 < 0` and `f(1.32812) = 0.01458 > 0`

`:.` Now, Root lies between `1.32422` and `1.32812`

`x_8 = (1.32422 + 1.32812)/2 = 1.32617`

`f(x_8) = f(1.32617) = 0.00621 > 0`


`10^(th)` iteration :

Here `f(1.32422) = -0.00213 < 0` and `f(1.32617) = 0.00621 > 0`

`:.` Now, Root lies between `1.32422` and `1.32617`

`x_9 = (1.32422 + 1.32617)/2 = 1.3252`

`f(x_9) = f(1.3252) = 0.00204 > 0`


`11^(th)` iteration :

Here `f(1.32422) = -0.00213 < 0` and `f(1.3252) = 0.00204 > 0`

`:.` Now, Root lies between `1.32422` and `1.3252`

`x_10 = (1.32422 + 1.3252)/2 = 1.32471`

`f(x_10) = f(1.32471) = -0.00005 < 0`


Approximate root of the equation `x^3-x-1=0` using Bisection method is `1.32471`

`n`	`a`	`f(a)`	`b`	`f(b)`	`c=(a + b)/2`	`f(c)`	Update
1	1	-1	2	5	1.5	0.875	`b = c`
2	1	-1	1.5	0.875	1.25	-0.29688	`a = c`
3	1.25	-0.29688	1.5	0.875	1.375	0.22461	`b = c`
4	1.25	-0.29688	1.375	0.22461	1.3125	-0.05151	`a = c`
5	1.3125	-0.05151	1.375	0.22461	1.34375	0.08261	`b = c`
6	1.3125	-0.05151	1.34375	0.08261	1.32812	0.01458	`b = c`
7	1.3125	-0.05151	1.32812	0.01458	1.32031	-0.01871	`a = c`
8	1.32031	-0.01871	1.32812	0.01458	1.32422	-0.00213	`a = c`
9	1.32422	-0.00213	1.32812	0.01458	1.32617	0.00621	`b = c`
10	1.32422	-0.00213	1.32617	0.00621	1.3252	0.00204	`b = c`
11	1.32422	-0.00213	1.3252	0.00204	1.32471	-0.00005	`a = c`

---

---