Binary search root of function using recursion

Question

I am trying to write a binary search function to find the root of function fun in the interval [𝑠𝑡𝑎𝑟𝑡,𝑒𝑛𝑑]:

Here is what I have which is close but missing the mark:

def binarySearchIter(fun, start, end,  eps=1e-10):
    '''
    fun: funtion to fund the root
    start, end: the starting and ending of the interval
    eps: the machine-precision, should be a very small number like 1e-10

    return the root of fun between the interval [start, end]
    '''

    root = (start + end)/2
    print(root)

    answer=fun(root)

    if abs(answer) <= eps:
        print(root)
        return root
    elif answer - eps > 0:
        binarySearchIter(fun, start, root, eps=1e-10)
    else:
        binarySearchIter(fun, root, end,  eps=1e-10)

Here is the function I am using to test:

def f(x):
return x ** 2 - 2

When I run: binarySearchIter(f, -3, 0, eps = 1e-10) I expect an answer of: -1.4142135623842478, however, root converges to -3 until it times out.

when I run binarySearchIter(f, 0, 3, eps = 1e-10) I am getting the correct answer of 1.4142135623842478.

I am obviously missing something that is making the function break depending on whether it gets (-3, 0) or (3,0).

Thank you for your help.

Answer 1

What you are seeing is that your function works only on increasing functions, which is true for x**2 - 2 between 0 and 3, but but does not work on decreasing functions, which is true for your function between -3 and 0.

There are several ways to fix your function. One way is to swap the values of start and end if fun(start) > fun(end). In other words, change your line root = (start + end)/2 to the three lines

if fun(start) > fun(end):
    start, end = end, start
root = (start + end)/2

This does slow down your routine, so there are better ways to do your routine. In particular, use iteration rather than recursion. Python does recursion pretty slowly compared to iteration.

However, your function is not robust. You should first check that fun(start) and fun(end) have differing signs. Your routine then would continue to redefine start and end so that their images continue to have opposite signs. If the signs are the same, there may not be a root of your function in that interval, and your routine definitely has no good way to decide which half of the interval to continue searching. One way to do this is to add these two lines before the ones I have already inserted:

if fun(start) * fun(end) > 0:
    raise 'Endpoints in binarySearchIter should yield opposite signs.'