找到函数的转折点

Question

找到函数的转折点

3

我希望能够找到函数输出第一个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

- Kurns

“first”是什么意思？是指范围内符合您条件的任何元素吗？还是最小的元素？ - Ray Toal

1

@RayToal 我对这个问题的理解（我承认可能有误）是，myFunction 对于小于某个数 N 的值返回 False，并对大于或等于 N 的所有值返回 True。目标是找到 N。因此可以使用二分查找来找到 N，同时调用 myFunction 不超过 35 次。但 next 将进行线性搜索，并且可能最多调用 myFunction 340亿次。 - user3386109

明白了，楼主想要找到一个独特的值 x，使得 f(x) 为真但 f(x-1) 为假。现在我理解了，但第一遍阅读时不太清晰。观察得很好。 :) - Ray Toal

1

没关系，我没有花太多时间阅读它。没事的。我认为你不可能比二分查找做得更好了。从中间开始，向左或向右走。即使知道转折点是靠近开头还是结尾，也不会比最简单的二分查找带来太多好处，因为一个2 ** 35的搜索空间只需要35个探测。 - Ray Toal

guess *= 2 - 这可能会将 guess 值移出搜索域。 - kfx

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kfx · Accepted Answer

这是一个经典问题，需要查找单调递增或递减函数的交叉点。正如你所猜测的那样，可以通过二分查找来解决。你的代码存在一些错误，这并不奇怪:

虽然这个想法很简单，但正确实现二分查找需要注意一些关于退出条件和中点计算的细节。

因此，在可能的情况下，应避免编写自己的二分查找。幸运的是，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