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

Question

我有一个包含字符串的Python列表，比如这样初始化：

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

我想要测试一个输入字符串，看看在这个列表中，哪个字符串是“字母顺序上比它小的最近的字符串”，哪个是“字母顺序上比它大的最近的字符串”，而且比较的时候不区分大小写（也就是说，不考虑发音，只看字母顺序，比如 a<b 这样的比较）。如果输入的字符串在列表中存在，那么“下面”和“上面”的结果都应该返回这个输入字符串。

这里有几个例子：

Input  | Below    |  Above   
-------------------------------
bat    | aardvark | cat      
aaa    | None     | aardvark 
ferret | dog      | fish     
dog    | dog      | dog

在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

你可以把这个问题换个说法：

给你一个已经排好序的字符串列表 l 和一个输入字符串 s，你的任务是找出 s 应该插入到 l 的哪个位置，这样插入后 l 仍然保持有序。

在你找到的位置 index，前一个位置 index-1 和后一个位置 index+1（如果存在的话）就是你需要关注的元素。为了找到这个位置，你可以使用一种叫做 二分查找 的方法。

Answer 3

这正是 bisect 模块的用处。它比单纯地遍历大列表要快得多。

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 上写的，所以请检查一下有没有拼写错误。