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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
一.无序表查找 def sequential_search(lis, key):
for i in lis:
if i = = key:
return lis.index(i)
else :
continue
else :
return False
if __name__ = = '__main__' :
LIST = [ 1 , 5 , 8 , 123 , 22 , 54 , 7 , 99 , 300 , 222 ]
result = sequential_search( LIST , 1231 )
print (result)
二.有序表查找 1. 二分查找(Binary Search)
def binary_search(lis,key):
low = 0
high = len (lis) - 1
time = 0
while low < high:
time + = 1
mid = int ((low + high) / 2 )
if key < lis[mid]:
high = mid - 1
elif key > lis[mid]:
low = mid + 1
else :
print ( "times: %s" % time)
return mid
print ( "times: %s" % time)
return False
if __name__ = = '__main__' :
LIST = [ 1 , 5 , 7 , 8 , 22 , 54 , 99 , 123 , 200 , 222 , 444 ]
result = binary_search( LIST , 99 )
print (result)
2. 插值查找
二分查找法虽然已经很不错了,但还有可以优化的地方。 有的时候,对半过滤还不够狠,要是每次都排除十分之九的数据岂不是更好?选择这个值就是关键问题,插值的意义就是:以更快的速度进行缩减。 插值的核心就是使用公式: value = (key – list [low]) / ( list [high] – list [low])
用这个value来代替二分查找中的 1 / 2
def binary_search(lis, key):
low = 0
high = len (lis) - 1
time = 0
while low < high:
time + = 1
# 计算mid值是插值算法的核心代码
mid = low + int ((high - low) * (key - lis[low]) / (lis[high] - lis[low]))
print ( "mid=%s, low=%s, high=%s" % (mid, low, high))
if key < lis[mid]:
high = mid - 1
elif key > lis[mid]:
low = mid + 1
else :
# 打印查找的次数
print ( "times: %s" % time)
return mid
print ( "times: %s" % time)
return False
|
本文转自小白的希望 51CTO博客,原文链接:http://blog.51cto.com/haoyonghui/2055623,如需转载请自行联系原作者