(Двоичный) Суммирование элементов списка

Question

Мне нужно суммировать элементы списка, содержащие все нули или единицы, так что результат равен 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++, тоже не работает).

У кого-нибудь есть указатели?

Также, как бы я сделал сумму, чтобы она была двоичной, а не просто десятичной с добавлением?

Answer 1

I need to sum the elements of a list, containing all zeros or ones, so that the result is 1 if there is a 1 in the list, but 0 otherwise.

Нет необходимости подводить весь список; вы можете остановиться на первом 1. Просто используйте any(). Он вернет True, если в контейнере имеется по меньшей мере одно значение правды, а False в противном случае, и это короткое замыкание (т.если истинное значение найдено в начале списка, оно не сканирует остальное). Удобно, 1 правдиво, а 0 - нет.

True и False работы как 1 и 0 в арифметическом контексте (Булевы являются подклассом целых чисел), но если вы хотите конкретно 1 и 0, просто обернуть any() в int().

Answer 2

Остановить создание вложенных списков.

Answer 3

I need to sum the elements of a list, containing all zeros or ones, so that the result is 1 if there is a 1 in the list, but 0 otherwise.

Что случилось с

int(1 in l) 

Answer 4

Вы фактически не хотите сумму; вы хотите знать, содержит ли upper или lower значение 1. Просто воспользоваться базовым синтаксисом контейнерного типа Пайтона:

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