Finding roots of a function with binary search and

Question

Could someone explain, please, why we need a difference between max and min to be less than error (of the root of the cubic equation)? What is the logic behind it? And why we need to return min?

Here's the code:

#include <stdio.h>
#include <stdlib.h>

double func(double x)
{
    return x * x * x  + 2 * x * x - 2;
}

double zeroFinder(double min, double max, double error)
{

    if ((max - min) < error)
    {
        return min;
    }
    double x = (max + min) / 2;

    if (func(x) < 0)
    {
        min = x;
    }
    else
    {
        max = x;
    }

    return zeroFinder(min, max, error);
}

int main(void)
{
     zeroFinder(0.0, 1.0, 0.01);
     zeroFinder(0.0, 1.0, 0.001);  
     zeroFinder(0.0, 1.0, 0.000001);    
     zeroFinder(0.0, 1.0, 0.0000000001);

     return 0;
} 

Answer 1

eps is the error limit will be accepted . In many Online judge(OJ) you will be seen that relative error less than 10^-6,10^-8 like that will be ignored . suppose eps =0.000001 so if the when the value of (max-min) is less than eps that means we reached at our desired result ...

Answer 2

The algorithm is implementing something known as the Bisection Method. The idea is to start with an interval (delimited by max and min in your case), evaluate the value at the midpoint and then shorten the interval appropriately.

This is exactly like binary search on a real line. However, since we are trying to find a real value, the function may not terminate on the real value in a finite number of iterations (e.g., when the answer is say sqrt(2)). Also, since the method calculates floating point variables, often you will not get the exact value. The iterative algorithm should however terminate in a finite set of iterations. Hence when the interval becomes small enough (i.e., when abs(max - min) < <some error value>, we can let the function terminate. What it means is that the answer obtained is within some error value of the correct answer.

As @Elyasin mentions in the comments, the code could return max, min or any value in between to be the answer. There may be some considerations about open and closed intervals, so returning (max + min) / 2.0 is also a safe bet.

Answer 3

With a recursive function, you have to have some base case for which the answer can be found without recursion, otherwise the recursion never stops.

The person who wrote the code chose to say that when the gap between the x-coordinates is less than the specified error, you are close enough to the root. When the two values are close enough, it really doesn't matter much which one is returned, but maybe (max + min) / 2.0 would be better still. But some value has to be returned as 'the x-coordinate which is close enough to the root'.

Note that the code is not safe. If both min and max evaluate to a negative quantity, it is probably not going to converge on a solution; if they both evaluate to a positive quantity, it is probably not going to converge on a solution.