|
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
，如需转载请自行联系原作者
