Python 不使用 for 循环查询列表

Question

我想在 python 列表中找到一对数字的和。

1. 列表已排序
2. 需要检查连续的组合
3. 避免使用 for 循环

我使用了 for 循环来完成工作并且工作正常。我想学习其他优化方法来获得相同的结果。

在不使用 for 循环的情况下，我可以通过其他方式获得相同的结果吗？

在这种情况下我如何使用二分搜索？

这是我的代码:

def query_sum(list, find_sum):
    """
    This function will find sum of two pairs in list
    and return True if sum exist in list
    :param list:
    :param find_sum:
    :return:
    """
    previous = 0
    for number in list:
        sum_value = previous + number
        if sum_value == find_sum:
            print("Yes sum exist with pair {} {}".format(previous, number))
            return True
        previous = number

x = [1, 2, 3, 4, 5]
y = [1, 2, 4, 8, 16]

query_sum(x, 7)
query_sum(y, 3)

这就是结果。

Yes sum exist with pair 3 4
Yes sum exist with pair 1 2

Answer 1

如果您的列表已排序(并且您只查看连续元素的总和)，您确实可以使用二分搜索，因为总和也将单调递增。在 N 个元素的列表中，有 N-1 个连续的对。您可以复制并粘贴在线找到的任何正确实现的二分搜索算法，并将条件替换为连续元素的总和。例如:

def query_sum(seq, target):
    def bsearch(l, r):
        if r >= l:
            mid = l + (r - l) // 2
            s = sum(seq[mid:mid + 2])
            if s == target:
                return mid
            elif s > target:
                return bsearch(l, mid - 1)
            else:
                return bsearch(mid + 1, r)
        else:
            return -1
    i = bsearch(0, len(seq) - 1)
    if i < 0:
        return False
    print("Sum {} exists with pair {} {}".format(target, *seq[i:i + 2]))
    return True

^{IDEOne Link}

您可以使用内置的 bisect 模块，但是您必须预先计算总和。这是一种更便宜的方法，因为您只需计算 log<sub>2</sub>(N)总和。

此外，此解决方案避免使用递归进行循环，但您最好编写像 while r >= l: 这样的循环。围绕逻辑而不是使用递归:

def query_sum(seq, target):
    def bsearch(l, r):
        while r >= l:
            mid = l + (r - l) // 2
            s = sum(seq[mid:mid + 2])
            if s == target:
                return mid
            elif s > target:
                r = mid - 1
            else:
                l = mid + 1
        return -1
    i = bsearch(0, len(seq) - 1)
    if i < 0:
        return False
    print("Yes sum exist with pair {} {}".format(*seq[i:i + 2]))
    return True

^{IDEOne Link}