在Python列表中查询“最接近”字符串（按字母顺序排列）

Question

我有一个Python字符串列表，例如初始化如下：

l = ['aardvark', 'cat', 'dog', 'fish', 'tiger', 'zebra']

我想根据这个列表测试一个输入字符串，并按字母顺序和不区分大小写找到“它下面最近的字符串”和“它上面最近的字符串”（即没有音标，只有a<b等）。如果输入存在于列表中，“belower”和“above”都应该返回输入。在

几个例子：

^{pr2}$

在Python中实现这一点最简洁的方法是什么？（目前我正在使用for循环遍历已排序的列表）

进一步澄清：我感兴趣的是简单的字典字母比较，而不是像Levenshtein或语音学这样的花哨的东西。在

谢谢

Answer 1

这是一个非常幼稚的实现，只适用于短列表：您可以很容易地遍历列表并将您的选择与每个列表进行比较，然后在第一次选择“大于”要比较的项时中断。在

for i, item in enumerate(l):
    if lower(item) > lower(input):
        break

print 'below: %s, above, %s' % (l[i-1], item)

Answer 2

这正是等分模块的用途。它将比仅仅迭代大型列表快得多。在

import bisect

def closest(haystack, needle):
    if len(haystack) == 0: return None, None

    index = bisect.bisect_left(haystack, needle)
    if index == 0:
        return None, haystack[0]
    if index == len(haystack):
        return haystack[index], None
    if haystack[index] == needle:
        return haystack[index], haystack[index]        
    return haystack[index-1], haystack[index]

上面的代码假设您已经将输入和列表清理为大写或小写。另外，我是在我的iPhone上写的，所以请检查是否有错别字。在

Answer 3

您可以将问题改为：

给定一个经过排序的字符串列表l和一个输入字符串s，在l中查找索引，其中{}应该被插入，以便{}在插入后保持排序。在

位于index-1和{}的l元素是您要查找的元素。为了找到索引，可以使用binary search。在