#!/usr/bin/python3

import numpy as np
import matplotlib.pyplot as plt
import math as math

#Q3a

def bracketing(f,a,b,n):
    for i in range(0,n):
        if f(a+(b-a)*i/n)*f(a+(b-a)*(i+1)/n)<0:
            return [a+(b-a)*i/n,a+(b-a)*(i+1)/n]
    raise Exception("Bisection routine has failed: interval doesn't contain root or sign changes undetected.")



def bisection(f,a,b,tol):
    curr = bracketing(f,a,b,1)
    while curr[1]-curr[0] > tol:
        mid = (curr[1]+curr[0])/2
        left=[curr[0], mid]
        right=[mid, curr[1]]
        if f(left[0])*f(left[1])<0:
            curr=left
        elif f(right[0])*f(right[1])<0:
            curr=right
    return (curr[0]+curr[1])/2