Двоичный поиск и списки

Question

class BinaryStringList(): 
    def __init_(self): 
     self.item = [] 

    def strAdd(self,item): 
     self.items.append(item) 

    def finditem(self, item): 

     if len(self)==0: 
      print("List is empty!") 
     else: 
      midpoint = len(self)//2 
      if self[midpoint]==item: 
       print("Item Found ", item) 
      else: 
       if item<self[midpoint]: 
        return finditem(self[:midpoint], item) 
       else: 
        return finditem(self[midpoint+1:], item) 

Поэтому, когда я нахожусь, у меня проблема при попытке добавить элементы в список. Если я сделаю что-то вроде:

alist = BinaryStringList() 
alist.strAdd("test1") 

мой код не указывает, что объект не имеет атрибута. Не уверен, почему он терпит неудачу, так как у меня есть почти тот же код для другой программы, кроме того, что find использует последовательный поиск, где это бинарный поиск.

Answer 1

В коде есть несколько синтаксических ошибок. Также рекурсия не работает таким образом, вам нужно получить базовое условие, которое возвращается. Это решение будет работать, но я настоятельно рекомендую вам решить более простые проблемы, используя рекурсию, чтобы понять, как это работает.

class BinaryStringList: 
    def __init__(self): # You had 1 _ after init 
     self.items = [] # Typo, should have been items. 

    def strAdd(self,item): 
     self.items.append(item) 

    def finditem(self, item): 
     return self.binser(self.items, item) 

    def binser(self, items, item): 
     if len(items)==0: 
      return 

     midpoint = len(items)/2 # len(self) means nothing, it should be len(self.items) 
     if items[midpoint]==item: 
      return item 
     else: 
      if item<items[midpoint]: 
       return self.binser(items[:midpoint], item) #self[:midpoint] means nothing, you needed self.items[:midpoint] 
      else: 
       return self.binser(items[midpoint+1:], item) 

binser = BinaryStringList() 
binser.strAdd(1) # You added a string here. Your logic won't work with string. 
binser.strAdd(2) 
binser.strAdd(3) 
binser.strAdd(5) 
binser.strAdd(8) 
binser.strAdd(9) 
binser.strAdd(10) 

print binser.finditem(1) 
print binser.finditem(10) 
print binser.finditem(5) 
print binser.finditem(11) 

(существует и другие способы решения двоичного поиска тоже - т.е. итеративного подход, прохождение низкого/высокого значения индекса, а не сплайсинг массива ввода). Попробуйте решить двоичный поиск, используя эти два подхода.

Двоичный поиск с прохождением низкого/высокого значения индекса, ваша подпись для binser будет выглядеть следующим образом: def binser(self, low, high, item):

Answer 2

Ваш код не работает, потому что вы ошибочно написали __init__. Вам нужно два подчеркивания с каждой стороны, или это просто странно названный метод. Так как вам не хватает __init__, используется __init__ (который не устанавливает атрибуты), и у вас нет атрибута или items. Вы должны исправить __init__ и использовать последовательное имя items:

class BinaryStringList(): 
    def __init__(self): # <-- Added extra trailing underscore 
     self.items = [] # Fixed name to be items, not item 

У вас есть много других проблем здесь (вы не поддерживаете порядок сортировки, поэтому бинарный поиск не будет работать, вы не реализовали __getitem__ так что self[midpoint] не будет работать, поэтому вам понадобится self.items[midpoint], недостаток __len__ означает, что len(self) не будет работать и т. Д.), Но эти два вопроса выше, что специально заставляет вас получить AttributeError.