二进制搜索 Python 中的解决方案

Question

我试着写了一个二进制搜索程序来找到满足

的最大x

x**2+(n-x-small)-(x-small)*(x-small-1)/2 <= maxSum

因为我不会直接解方程。只有 x 是未知的。 lst 包含一系列可能的整数值

下面的代码不知何故没有给出任何 return 值，尽管它可以在每个条件下打印。几个小时以来，我一直坚持使用以下代码，不确定哪里出了问题。

def binarySearch(self, lst, n, small, maxSum):
        m=len(lst)
        if m==1: 
            x=lst[0]
            a=x**2+(n-x-small)-(x-small)*(x-small-1)/2
            if a<=maxSum:
                return x
            else:
                return x-1
        else:
            j=m//2
            x=lst[j]
            a=x**2+(n-x-small)-(x-small)*(x-small-1)/2
            if a==maxSum:
                return x
            elif a > maxSum:
                self.binarySearch(lst[:j], n, small, maxSum)
            elif a < maxSum:
                self.binarySearch(lst[j:], n, small, maxSum)

Answer 1

递归的问题是你必须return递归函数。

你没有在 elif 语句的末尾这样做，这就是为什么它进行了计算但在从递归返回的路上丢失了答案。 :)

只需在调用递归之前添加 2 returns，如下所示：

def binarySearch(self, lst, n, small, maxSum):
m = len(lst)
if m == 1:
    x = lst[0]
    a = x ** 2 + (n - x - small) - (x - small) * (x - small - 1) / 2
    if a <= maxSum:
        return x
    else:
        return x - 1
else:
    j = m // 2
    x = lst[j]
    a = x ** 2 + (n - x - small) - (x - small) * (x - small - 1) / 2
    if a == maxSum:
        return x
    elif a > maxSum:
        return binarySearch(lst[:j], n, small, maxSum)
    elif a < maxSum:
        return binarySearch(lst[(j + 1):], n, small, maxSum)

elif a > maxSum:

return binarySearch(lst[:j], n, small, maxSum)

elif a < maxSum:

return binarySearch(lst[(j + 1):], n, small, maxSum)

二进制搜索 Python 中的解决方案

binary search for a solution in Python

python

algorithm

return-value

binary-search