//Bisection is the C implementation of the pseudocodes discussed in class

#include <stdio.h>
#include <math.h>

double bisect(double, double);
double f(double);

main()
{
	double xleft,xright;
	double xmiddle;

	printf("Input bracket for root\n");
	printf("\tLeft\n");
	scanf("%lg",&xleft);
	printf("\tRight\n");
	scanf("%lg",&xright);

	xmiddle=bisect(xleft,xright);

	printf("Best estimate of root is:%lg\n",xmiddle);
	return 0;
}

double bisect(double left, double right)
//input to this subroutinue is the left and right value of the bracket
//output will be the best estimate of the zero at the middle of the last interval
{
//declarations
	double middle;
	double fleft, fright, fmiddle;
	double tol, error;

//initializations

	tol=5.0e-3;
	fleft=f(left);
	fright=f(right);

//top of loop
	do
	{
		middle=(left+right)/2.0;
		fmiddle=f(middle);

		//determine which half of the interval contains the root
		if(fleft*fmiddle <= 0.0)
			{
			//the root is in the left subinterval
			right=middle;
			fright=fmiddle;
			}
		else
			{
			//the root is in the right subinterval
			left=middle;
			fleft=fmiddle;
			}

		//check for relative error
		error=fabs((right-left)/middle);
	}while(error>tol);

	//send result back to main
	return middle;
}

//function to be used
double f(double xx)
{
	return xx*xx*xx-2.0;
}