使用二进制搜索进行简单的自动完成

Question

在元组列表中（第一个是字符串，第二个是整数）我必须使用二进制搜索找到第一个元素以输入字符串开头的所有元组。在此之前，我通过 tuple 的第一个元素对元组列表进行了词典排序，然后使用二进制搜索，将第一个元素等于输入字符串的元组添加到新列表中。这是我的代码

def binary_search(x,list):  
    l=0
    r=len(list)-1
    while l<=r:
        m=(r-1)/2+l
        m=int(m)
        if list[m][0][0:len(x)]==x:
            return list[m]
        elif list[m][0][0:len(x)]<x:
            l=m+1
        elif list[m][0][0:len(x)]>x:
            r=m-1
    return -1

然后我将我想要的元组列表添加到新列表

new_list=[]
s=input()
lexicographic_sort(list) #function that sorts using lambda
a=binary_search(s,list)
while a!=-1:
    new_list.append(a)
    list.remove(a)
    a=binary_search(s,list)

print(new_list)

问题是当我只输入 1 个字符时，我得到了我想要的结果，但是输入超过 1 个字符时，程序就死机了。放置超过 1 个字符时更令人困惑的问题是，当我删除 while 循环只是为了调用一个二进制搜索时，它 returns 我是一个元组，所以我不知道为什么我的程序会冻结。
该列表是 [('school', 312), ('bus', 421), ('scheme', 53), ('and', 423), ('maybe', 143), ('schemes', 53), ('ands', 423), ('maybes', 143), ('schemess', 53), ('andsss', 423), ('maybesss', 143)] 输入 1:sc
输出：[('schemess', 53), ('school', 312), ('scheme', 53), ('schemes', 53)]
输入 2:may
输出：（冻结）

Answer 1

在二进制搜索中，一个主要步骤是查看中间元素，如 https://en.wikipedia.org/wiki/Binary_search_algorithm（以及其他地方）所述

m = (r+l) // 2

你有

m=(r-1)/2+l

例如9和11的中间就是10/2+9 = 14，这是不对的。这可能会导致您查看对于数组来说太大的索引，从而以 IndexError 退出程序。

您需要使用 // 来保证整数结果。在这种情况下，需要向下舍入。

尽管如此，您确实应该清楚您遇到了 IndexError 异常。不知道它应该冻结是怎么回事。那部分没有意义。

Answer 2

应该计算 "moving middle" 元素 m=(r-l)/2+l 但你有 m=(r-1)/2+l.

应该是：

def binary_search(x,list):  
    l=0
    r=len(list)-1
    while l<=r:
        m=(r-l)/2+l
        m=int(m)
        if list[m][0][0:len(x)]==x:
            return list[m]
        elif list[m][0][0:len(x)]<x:
            l=m+1
        elif list[m][0][0:len(x)]>x:
            r=m-1
    return -1

参考：python binary search

Answer 3

内置排序会正确排序...不需要 lamda

terms = sorted(terms)

有一个用于排序列表的内置二进制搜索...

import bisect
idx = bisect.bisect(ordered_list_to_search,term)
print("Found: ",idx)

所以你可以说（因为看起来所有数值都大于或等于 1）

idx = bisect.bisect_right(terms,(search_term,0))
if idx < len(terms):
    print(terms[idx])
print("Nothing found...")

使用二进制搜索进行简单的自动完成

Making simple autocomplete using binary search

python

binary-search