使用in运算符可以检查一个单词是否在单词表中, 但这很慢, 因为它是按顺序查找单词。
由于单词是按照字母顺序排序的,我们可以使用两分法 (也称二叉树搜索) 来加快速度, 类似于在字典中查找单词的方法。你从中间开始,如果你要找的单词在中间的单词之前,你查找前半部分,否则你查找后半部分。
不管怎样, 你都会将搜索范围减小一半。 如果单词表有 113,809 个单词, 你只需要 17 步就可以找到这个单词,或着得出单词不存在的结论。
编写一个叫做in_bisect的函数,接受一个已排序的列表和一个目标值作为参数,返回该值在列表中的位置,如果不存在则返回None。
或者你可以阅读bisect模块的文档并使用它!
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| def in_bisect(t,a):
"""列表t，单词a，看单词是否在列表内，在的话返回单词的位置。
列表里的单词，必须是已经按字母顺序排好序的。
"""
s1 = int((len(t))/2)
s = s1 #如果a在列表内，s保存a的下标
while s1 > 0:
if a == t[s1]:
return s
elif a > t[s1]:
t = t[s1:]
s1 = int(len(t)/2) #在循环过程中，确保s和s1所指的是同一个元素。
#print(a,"的位置大于",s)
s += s1
else:
t = t[:s1]
s1 = int(len(t)/2)
#print(a,"的位置小于等于",s)
s -= s1
return None
t1 = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q']
in_bisect(t1,'c')
|
s和s1这两个变量，保存的是列表元素的下标。在循环过程中，确保s和s1所指的是同一个元素，即：s保存的是元素在完整列表里的下标，s1保存的是元素在切片后的列表里的下标，在两个列表里，第s个元素和第s1个元素（都从0开始）是同一个元素。
因为涉及到除法然后取整，写代码的时候老是担心误差，总想对下标加个1或减个1，所得到的结果越来越离谱，后来干脆不加不减，反倒顺顺利利的。真的就是做多错多。代码虽然是我写出来的，但实际上我对它的运行过程并不是了如指掌。
我画了一个图来跟踪代码运行时的状态，不能叫堆栈图，就单纯是为了跟踪变量在一次循环后会如何变化。
这是作者的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| import bisect
def make_word_list():
word_list = []
fin = open('words.txt')
for line in fin:
word = line.strip()
word_list.append(word)
return word_list
def in_bisect(word_list, word):
"""通过二分法，检查一个单词是否在一个列表里
前置条件：列表里的单词是已排序的
returns：如果单词在，返回True，否则返回False
"""
if len(word_list) == 0:
return False
i = len(word_list)//2
if word_list[i] == word:
return True
if word_list[i] > word:
return in_bisect(word_list[:i],word)
else:
return in_bisect(word_list[i+1:],word)
def in_bisect_cheat(word_list,word):
i = bisect.bisect_left(word_list,word)
if i == len(word_list):
return False
return word_list[i] == word
if __name__ == '__main__':
word_list = make_word_list()
for word in ['aa', 'alien', 'allen', 'zymurgy']:
print(word, 'in list', in_bisect(word_list, word))
for word in ['aa', 'alien', 'allen', 'zymurgy']:
print(word, 'in list', in_bisect_cheat(word_list, word))
|
用了递归，比我写的高明很多。我的代码一比较，就跟直肠子似的，没有一点弯弯绕。
但是作者并没有返回单词在列表的下标，只是简单返回一个True或False。