二进制搜索和列表

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)

所以，我发现我有一个问题，就是当我试图将项目添加到列表中时。如果我做一些类似的事情：

^{pr2}$

我的代码在声明对象没有属性时失败。不知道为什么会失败，因为我对另一个程序有几乎完全相同的代码，除了查找使用的是顺序搜索，因为这是一个二进制搜索。在

Answer 1

您的代码失败，因为您拼写错误__init__。每边需要两个下划线，或者只是一个奇怪的命名方法。由于缺少__init__，所以使用默认的__init__（不设置属性），并且没有item或{}属性。您需要修复__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]，缺少{}意味着{}也无法工作，等等），但是上面的两个问题正是您获得{}的具体原因。在

Answer 2

代码中有多个语法错误。递归也不是这样工作的，你需要有一个返回的基本条件。这个解决方案可以工作，但我强烈建议您使用递归来解决更简单的问题，以了解它是如何工作的。在

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):