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

Question

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

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

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

不知何故，下面的代码没有给出任何返回值，尽管它可以在每个条件下打印。我已经被以下代码困扰了好几个小时，不确定出了什么问题

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

递归的问题是必须返回递归函数

您在elif语句末尾没有这样做，这就是为什么它进行了计算，但在从递归返回的过程中丢失了答案。：）

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

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>；最大和：

返回二进制搜索（lst[：j]，n，small，maxSum）

艾利夫a<；最大和：

returnbinarySearch（lst[（j+1）：]，n，small，maxSum）