Unbounded Binary Search (Finding the point where a monotonically increasing function becomes zero)

Question

I am trying to write code that finds the point where a monotonically increasing function becomes zero. I am using Unbounded Binary Search for this.

I tried the following code but it just gives me the point where the function becomes positive first time. It is also not all that accurate. I want to have an accuracy of 12 decimal places.

# Python3 program for Unbound Binary search.

# Let's take an example function as
# f(x) = x^2 - 10*x - 20
# Note that f(x) can be any monotonocally
# increasing function
def f(x):
    return (x * x - 10 * x - 20)


# Returns the value x where above function
# f() becomes positive first time.
def findFirstPositive():
    # When first value itself is positive
    if (f(0) > 0):
        return 0

    # Find 'high' for binary search
    # by repeated doubling
    i = 1
    while (f(i) <= 0):
        i = i * 2

    # Call binary search
    return binarySearch(i / 2, i)


# Searches first positive value of
# f(i) where low <= i <= high
def binarySearch(low, high):
    if (high >= low):

        # mid = (low + high)/2
        mid = low + (high - low) / 2;

        # If f(mid) is greater than 0
        # and one of the following two
        # conditions is true:
        # a) mid is equal to low
        # b) f(mid-1) is negative
        if (f(mid) > 0 and (mid == low or f(mid - 1) <= 0)):
            return mid

            # If f(mid) is smaller than or equal to 0
        if (f(mid) <= 0):
            return binarySearch((mid + 1), high)
        else:  # f(mid) > 0
            return binarySearch(low, (mid - 1))

            # Return -1 if there is no positive
    # value in given range
    return -1


# Driver Code
print("The value n where f() becomes " +
      "positive first is ", findFirstPositive())

Output:

The value n where f() becomes positive first is  12.0

I am new to Python and any help will be appreciated.

Thank you.

Answer 1

How about something like this?

def f(x):
    return (x * x - 10 * x - 20)

def findFirstPositive():
    if (f(0) > 0):
        return 0
    i = 1
    while (f(i) <= 0):
        i = i * 2
    return binarySearch(i / 2, i)

def binarySearch(low, high):
    if (high >= low):
        mid = (low + high)/2
        if abs(f(mid)) < 1e-10:
            return mid
        if f(mid) <= 0:
            return binarySearch(mid, high)
        else:
            return binarySearch(low, mid)
    return -1

print("The value n where f() becomes positive first is ", findFirstPositive())

Also, note that your function - x*x-10*x-20 - isn't actually monotonically increasing everywhere; however, your code only starts searching from x=0 so it still works.