0

我的任务是在单词列表上创建二进制搜索，我提出了 2 个实现（显然还没有提出尚未找到该单词的情况，但这还不是问题），但是当列表缩小到我正在寻找的单词，我的函数没有完成，而是继续运行，直到超过最大递归深度。

我把它打印出来，它清楚地显示了这个词dasList[mid]，并一遍又一遍地显示它，直到它最终放弃。

def _bisect2(dasList, word):
    mid = int(len(dasList)/2)
    if word.lower() > dasList[mid].lower():
        return _bisect2(dasList[mid: len(dasList)], word)            
    if word.lower() < dasList[mid].lower():
        return _bisect2(dasList[0: mid], word)
    else:
        return mid

这是由

print(_bisect2(fileList, input('Please type a word')))

我正在使用 Python 3.0 解释器。有什么建议么？

4

3 回答 3

1

您的实现（几乎）对我有用（并且没有显示您使用我的预排序输入描述的行为）。我假设您已经对输入文件进行了排序？下面发布了一个稍微修改（工作）的示例。

def _bisect2(dasList, word,lidx=0):
    mid = int(len(dasList)/2)
    if word.lower() > dasList[mid].lower():
        return _bisect2(dasList[mid:], word,lidx=lidx+mid)            
    elif word.lower() < dasList[mid].lower():
        return _bisect2(dasList[:mid], word,lidx=lidx)
    return lidx+mid

words=sorted(["one","two","three","four","five","twenty","foo"])
print (words)
print (_bisect2(words,'three'))

请注意，您正在返回最后一个部分列表中的索引（始终为 0）...

于 2012-05-31T01:37:21.633 回答
1

这对我来说很好。请注意，最后返回的索引将始终是最小列表中单词的索引，而不是原始列表的索引。

另请参阅>比较不会再次对列表执行 len，它只是迭代到最后。如果您要迭代到最后，切片语法允许您省略最后一个数字。

words = "The quick brown fox jumped over the lazy dog".split()

def bisect(words, word):
    mid = int(len(words)/2)
    if word.lower() > words[mid].lower():
        return bisect(words[mid:], word)
    elif word.lower() < words[mid].lower():
        return bisect(words[0:mid], word)
    return mid

words = sorted(words)
print bisect(words, 'dog')
于 2012-05-31T01:49:03.470 回答
1

为什么不使用 Python 的bisect模块？

来自文档的食谱：

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

例子：

>>> a = ['alfred','edward','mary','susan','thomas','wilma']
>>> index(a, 'mary')
2
>>> index(a, 'martha')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 6, in index
ValueError
于 2012-05-31T02:18:31.913 回答