1

我需要对包含所有零或一的列表的元素求和，以便如果列表中有 1，则结果为 1，否则为 0。

def binary_search(l, low=0,high=-1):
    if not l: return -1
    if(high == -1): high = len(l)-1
    if low == high:
        if l[low] == 1: return low
        else: return -1
    mid = (low + high)//2
    upper = [l[mid:high]]
    lower = [l[0:mid-1]]
    u = sum(int(x) for x in upper)
    lo = sum(int(x) for x in lower)
    if u == 1: return binary_search(upper, mid, high)
    elif lo == 1: return binary_search(lower, low, mid-1)
    return -1

 l = [0 for x in range(255)]
 l[123] = 1
 binary_search(l)

我用来测试的代码

u = sum(int(x) for x in upper)

在解释器中工作正常，但给了我错误

TypeError：int() 参数必须是字符串或数字，而不是“列表”

我刚刚开始使用python，无法弄清楚出了什么问题（我用c ++编写的版本也不起作用）。

有没有人有任何指示？

另外，我将如何求和，使其成为二进制异或，而不仅仅是十进制加法？

4

4 回答 4

4

您实际上并不想要总和；你想知道是否upper或lower包含一个1值。只需利用 Python 的基本容器类型语法：

if 1 in upper:
    # etc
if 1 in lower:
    # etc

顺便说一句，您收到错误的原因是因为您在尝试拆分时正在包装upper并lower使用额外的嵌套列表l（顺便重命名此变量！！）。你只想这样拆分它：

upper = the_list[mid:high]
lower = the_list[:mid-1]

最后，值得注意的是，您的逻辑很奇怪。这不是传统意义上的二分搜索。看起来您正在实现“查找1此列表中第一次出现的索引”。即使忽略已经有一个内置函数可以执行此操作的事实，只需遍历整个列表直到找到1. 现在，你有O(nlogn)时间复杂度（加上一堆额外的一次性循环），考虑到输出可以通过以下方式及时复制，这非常愚蠢O(n)：

def first_one(the_list):
    for i in range(len(the_list)):
        if the_list[i] == 1:
            return i
    return -1

或者当然更简单地使用内置函数index：

def first_one(the_list):
    try:
        return the_list.index(1)
    except ValueError:
        return -1
于 2013-07-01T16:03:34.227 回答
3

我需要对包含所有零或一的列表的元素求和，以便如果列表中有 1，则结果为 1，否则为 0。

有什么问题

int(1 in l)
于 2013-07-01T16:03:10.527 回答
2

停止制作嵌套列表。

upper = l[mid:high]
lower = l[0:mid-1]
于 2013-07-01T16:01:53.210 回答
2

我需要对包含所有零或一的列表的元素求和，以便如果列表中有 1，则结果为 1，否则为 0。

无需总结整个列表；您可以在第一个 1 处停止。只需使用any(). True如果容器中至少有一个真值，它将返回，False否则，它会短路（即，如果在列表的前面找到一个真值，它不会扫描其余的值）。方便的是，1 是真的，0 不是。

True并在算术上下文中作为 1 和 0 工作（布尔值是整数的子类），但如果您特别想要 1 和 0 ，False只需将any().int()

于 2013-07-01T16:05:07.193 回答