Binäre Suche und Listen

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) 

Also wo ich finde ich habe ein Problem ist, wenn Sie versuchen, Elemente zur Liste hinzuzufügen. Wenn ich etwas wie:

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

mein Code fehlschlägt, die Angabe hat kein Attribut. Nicht sicher, warum es scheitert, da ich fast genau den gleichen Code für ein anderes Programm habe, außer dass der Fund eine sequenzielle Suche verwendet, bei der es sich um eine binäre Suche handelt.

Answer 1

Sie haben mehrere Syntaxfehler in Ihrem Code. Auch Rekursion funktioniert nicht so, Sie müssen eine Basisbedingung haben, die zurückkehrt. Diese Lösung wird funktionieren, aber ich schlage vor, dass Sie einfachere Probleme mit Rekursion lösen, um zu verstehen, wie es funktioniert.

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) 

(es gibt auch andere Möglichkeiten, zu Binärsuche Lösung - d.h. iterativer Ansatz, low/high-Index-Werte vorbei anstatt Spleißen der Eingabeanordnung). Versuchen Sie, die binäre Suche mit diesen beiden Ansätzen zu lösen.

Binary Suche mit niedrigen/hohen Indexwerte vorbei, wird Ihre Unterschrift für binser wie folgt aussehen: def binser(self, low, high, item):

Answer 2

Ihr Code schlägt fehl, weil Sie __init__ falsch geschrieben haben. Sie benötigen zwei Unterstriche auf jeder Seite, oder es ist nur eine seltsam benannte Methode. Da Ihnen __init__ fehlt, wird der Standardwert __init__ (der keine Attribute festlegt) verwendet, und Sie haben kein item oder items Attribut. Sie müssen die __init__ zu beheben, und einen einheitlichen Namen für items verwenden: hier

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

Sie haben viele anderen Probleme (SieFormal Aufrechterhaltung nicht sortierter Reihenfolge, so binäre Suche wird nicht funktionieren, haben Sie nicht umgesetzt __getitem__ so self[midpoint] wird nicht funktionieren, so würden Sie benötigen self.items[midpoint], Mangel an __len__ bedeutet len(self) wird nicht funktionieren, etc.), aber die beiden oben genannten Probleme sind, was Sie speziell die AttributeError bekommen.