python - 预算内的一对商品价格

Question

我正在尝试练习二进制搜索。目的是找到预算范围内的一对项目价格。

def binary_search(arr, lo, hi, x):
    while lo < hi: 
        count = 0
        sum = arr[lo] + arr[hi]
        if sum <= x:
            result = [arr[lo], arr[hi]]
            print(result)
            count += 1
            return binary_search(arr, lo, hi-1, x)
        else:
            return binary_search(arr, lo, hi-1, x)

A = [1, 2, 3, 4, 6, 7, 8]
print(binary_search(A, 0, len(A)-1, 10))

如您所见，我只能找到第一项和其他项：

(1,8)
(1,7)
(1,6)
(1,5)
(1,4)
(1,3)
(1,2)

当然，我可以再次使用

return binary_search(arr, lo+1, hi, x)

在函数中找到其他对，但这并不理想。

或者我可以以非常简单的方式使用 itertools。

from itertools import combinations
A = [1, 2, 3, 4, 6, 7, 8]
budget = 10
comb = combinations(A, 2)
answer = []

for i in list(comb):
    if sum(i) <= 10:
        print(I)
        answer.append(i)
print(len(answer))
print(answer)

有没有更好的方法来使用二进制搜索来处理这个问题。任何帮助都非常感谢！

标签： pythonbinary-search