As for the bisection interval, I am not sure the basic c=(a+b)/2 is not enough. Can you provide an example where it fails?Sure. I've experienced this myself, for example, when doing the research cited here:
http://pubs.acs.org/doi/abs/10.1021/es202359j
Unfortunately, my Lab doesn't have our report version of the work up on the web yet (I believe it should be freely available at some point, but they're re-doing the library).
In addition, I knew about this particular effect before I started that work, so I must have run into it earlier.
In most cases, naive bisection works fine. That's especially true if you use pretty loose tolerances-- for example, you if only want to identify the zero to a relative tolerance of 1e-6 or something coarse like that. But this work demanded very tight tolerances (because the output gets used in a time-marching numerical simulation that may iterate on time steps, and hence has to be very repeatable no matter what the initial condition). In this work, the relative tolerance was about 2e-15, and the absolute tolerance about 1e-18 (on a machine with double-precision epsilon about 2e-16).
By the way, if you're testing for convergence according to a bracket on the value, then you want to know (b-a) anyhow. So there's no reason not to go ahead and use it to bisect the interval as well.
Another interesting implementation detail-- at very tight relative tolerances, you also need to calculate the terminating bracket width based on the larger of |b| and |a|-- due to floating point effects, if you find the terminating bracket width by applying the relative tolerance to the smaller value, you can occasionally run into a problem where adding that width to one of a or b fails to change the estimated value.