无界二分搜索（找到单调递增函数变为零的点）

Question

我正在尝试编写代码来找到单调递增函数变为零的点。为此，我正在使用 无界二进制搜索。

我尝试了下面的代码，但它只是告诉我函数第一次变为正的点。它也不是那么准确。我想要精确到小数点后 12 位。

# 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())

输出：

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

我是 Python 的新手，我们将不胜感激。

谢谢。

Answer 1

这样的怎么样？

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())

此外，请注意您的函数 - x*x-10*x-20 - 实际上并不是到处都在单调递增；但是，您的代码仅从 x=0 开始搜索，因此它仍然有效。

无界二分搜索（找到单调递增函数变为零的点）

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

python

binary-search