python - 寻找函数的转折点

Question

我想要为我的函数输出 True 的第一个值。我目前有一个搜索工作正常，但我认为仍然有点低效。谁能建议更好的二进制搜索？我的代码在下面，经过简化。

guess = 2
limits = [2, 2**35] #The search area

while True:
    if myFunction(guess) == False:
        limits[0] = max(limits[0], guess) #Limit the search area
        guess *= 2
    else:
        limits[1] = min(limits[1], guess) #Limit the search area
        guess = int((limits[0] + limits[1])/2) #The guess is the midpoint of the search area
        if myFunction(guess) == True and myFunction(guess-1) == False:
            return guess

Answer 1

这是寻找单调递增或递减函数的水平交叉点的经典问题。如您所料，它可以通过 binary search 解决。您的代码有一些错误，这并不奇怪:

Although the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation.

因此，您应该尽可能避免编写自己的二进制搜索。幸运的是，Python 提供了一个库模块 bisect 可以为您完成这项工作。

from bisect import bisect_left

MIN = 2
MAX = 2**35

def search(f):
   # Finds the first position of `True` in `f`
   return bisect_left(f, True, lo=MIN, hi=MAX + 1)

不要对 bisect 仅适用于可索引对象的事实感到困惑:不需要创建包含 2**35 元素的列表。您可以使用生成器对象，而不是使用 __getitem__ 语法。为此，将您的函数封装在一个类中，并定义 getter 方法，该方法将为感兴趣点左侧的所有参数值返回 False，否则返回 True。

def myFunction1(index):
   return index >= 1456
def myFunction2(index):
   return index >= 2
def myFunction3(index):
   return index >= MAX - 1

class F:
   def __init__(self, f):
      self.f = f
   def __getitem__(self, index):
      return self.f(index)

# testing code
print(search(F(myFunction1))) # prints 1456
print(search(F(myFunction2))) # prints 2
print(search(F(myFunction3))) # prints MAX - 1