参考书籍：《算法之美——Python语言实现》
学习Python算法的同学极力推荐此书
前言：正在准备打蓝桥杯的博主复习到了检索算法，为了防止爆零，因而写下了这篇博客巩固知识，废话不多说，开始今天的正题。
目录一、线性查找二、二分查找三、插值查找四、斐波那契查找五、分块查找六、哈希查找七、回溯查找
一、线性查找代码如下：
def linefind(arr,key):
i,n=0,len(arr)
while i
代码输出：
待查找的元素列表 [100, 22, 44, 0, 2, 492, 3, 20, 38]
元素5没有找到
算法评价：
优点：元素列表没有要求，思路简单。缺点：效率不高。
代码解释：
因为过于简单我也就不过多的解释了。
二、二分查找
代码如下：
def erfen(arr,key):
left,right=0,len(arr)
while left<=right:
mid=(right-left)//2
if arr[left+mid]key:
right=left+mid-1
else:
return left+mid
return -1
ls=[0,2,3,5,8,9,12,30,40,50,55]
print("查找列表",ls)
key=55
x=erfen(ls,key)
if x==1:
print('列表里没有%d元素'%(key))
else:
print("在列表里找到元素%d,其下标为%d"%(key,x))
代码输出：
查找列表 [0, 2, 3, 5, 8, 9, 12, 30, 40, 50, 55]
在列表里找到元素55,其下标为10
算法评价：
缺点：需要列表为有序列表。优点：思路简单，算法较快。
代码解释：
就是一个简单的二分思想算法，也没有什么特别需要去注意的。当然，二分查找自然也可以使用递归的方法解决问题。
三、插值查找
代码如下：
def chazhisearch(arr,key):
left,right=0,len(arr)-1
while leftarr[mid]:
left=mid+1
else:
return mid
return -1
ls=[0,2,5,7,9,20,30,40,50]
key=50
print('查询列表为',ls)
print('查询值为',key)
x=chazhisearch(ls,key)
if x==1:
print('%d没有找到'%(key))
else:
print('查找值%d在列表里的下表值为%d'%(key,x))
代码输出：
查询列表为 [0, 2, 5, 7, 9, 20, 30, 40, 50]
查询值为 50
查找值50在列表里的下表值为8
算法评价：
缺点：需要列表为有序列表并且需要列表元素大小分布均匀。优点：思路简单，算法较快。其实这个算法就是对“mid”进行了优化。但是当列表元素大小分布不均匀时，该算法会非常的慢。
代码解释：
没有什么需要去注意的，所以仍然没有什么好解释的。
四、斐波那契查找
代码如下：
def FibonaSearch(arr,key):
a,b,c=len(arr),1,[1,1]
while c[b]<=a:
c.append(c[b]+c[b-1])
b+=1
print("生成的斐波那契数列",c)
left,right=0,a-1
d=c[b]
print("生成的最大的斐波那契数",d)
i=0
while iarr[mid]:
left=mid+1
j-=2
else:
print("查找次数:%s"%(k))
if mid<=right:
return mid
else:
return right
print("查找次数：%s"%(k))
return False
key=70
ls=[0,3,5,7,10,30,50,70,80,100]
x=FibonaSearch(ls,key)
if x==False:
print("数%d在列表里没有找到！")
else:
print("查找数%d在列表里的下标为%d"%(key,x))
代码输出：
生成的斐波那契数列 [1, 1, 2, 3, 5, 8, 13]
生成的最大的斐波那契数 13
[0, 3, 5, 7, 10, 30, 50, 70, 80, 100, 100, 100, 100]
left=0,mid=12,right9
left=0,mid=7,right11
查找次数:2
查找数70在列表里的下标为7
算法评价：
缺点：难以理解而且这段代码是有漏洞的(无法查询列表第一个元素的位置。当然，我们知道它的位置是0，但是程序会返回找不到，博主已经向原著作者反应，但是他不张我，裂开)。优点：使用斐波那契数列对“mid”进行优化大大提高了查询效率。如果斐波那契数列的长度为n，顶多查询n-1次。但是博主并不认为斐波那契查找特别优于二分法的查找方法。读者可以参考这篇文章，点这。在理论上，对半二分法的速度是二分法中步数最少的。但是在实际实现中，斐波那契二分查找算法因为每一步的计算 简单，所以虽然牺牲部分步数，但是总的效率是更高的 。这个是那篇文章的结论。
代码解释：
定义一个函数，首先创建一个斐波那契数列。这个斐波那契数列倒数第二个元素值小于给定列表长度，倒数第一个元素值大于给定列表长度。然后将给定列表用给定列表的最后一个元素补位到长度为斐波那契数列最后一个元素值。定义“j”，“k“分别用于记录斐波那契数列元素个数和查找次数。***然后思路就与二分查找它们一样了。斐波那契数列查找就是对”mid"进行优化。***从大到小依次遍历构造好了的斐波那契数列。将查询指定列表的索引值即“mid”赋值为对应的斐波那契数列元素值。当索引值对应元素大于查询元素，将查询范围缩小到“mid”右边一个步长，即将“right”赋值为“mid”-1。缩小查询步长(这个查询步长由当前斐波那契数列元素值决定)当索引值对应元素小于查询元素，将查询范围缩小到“mid”左边一个步长，即将“left”赋值为“mid”+1。缩小查询步长(同样这个查询步长由当前斐波那契数列元素值决定)。如此循环往复，直到找到查询元素，或者来到最后一步。当对斐波那契数列的遍历来到了第一、第二个元素即”j“<2，直接令”mid”=“left”。因为此时步长为1了，一定可以判断出列表中是否存在查询元素。如果列表中不存在查询元素，函数返回“False”。如果列表中存在查询元素，函数返回查询值的下标索引。这个就是整个函数的运行机制了。
疑难解决：
循环中的“j”-=2：“mid”是由“left”与步长共同决定的。当索引值对应元素小于查询元素时，”left"被赋值为了“mid"+1，此时下一次的索引”mid“已经增大一次。使用“j”-=1自然是没有问题，只不过会增加查询范围。而使用“j”-=2，可以进一步缩小查询范围。博主表达能力有限，还请读者尽力理解，又是emo的一天。
五、分块查找
代码如下：
from 线性查找 import linefind
def blocksearch(arr,key,index,n):
max0,j=-1,0
for i in index:
j+=1
if key<=i:
max0=i
break
if max0==-1:
return -1
print('块内最大值为{}'.format(max0))
x=linefind(arr[(j-1)*n:(j*n-1)],key)
print('线性查找结果%d'%(x))
if x==-1:
return -1
else:
return (j-1)*n+x
ls=[1,4,2,8,3,10,89,20,19,50,200,128,121,120,110]
index=[8,89,200]
key=2
x=blocksearch(ls,key,index,5)
if x==1:
print('%d在列表里不存在'%(key))
else:
print('%d在列表里的下标为%d'%(key,x))
代码输出：
块内最大值为8
线性查找结果2
2在列表里的下标为2
算法评价：优点：比一般的线性查找更快。缺点：块内可以无序，块间必须有序，从做题的角度上说，这个算法就拿来图一乐，锻炼锻炼思维就好。题目给出的数列总不会那么刚好。其他角度我也不懂。但是存在即合理吧。
代码分析：此段代码，先导入之前的线性查找函数。分块查找函数接收待查列表、查找的值、不同块内的最大值构成的列表、块的长度。max0用于记录查找值所在块内的最大值。j用于记录查找值所在块的块的位置(由于是先加1后判断，所以索引从1开始)。开始遍历不同块内的最大值构成的列表，如果查找值比列表中的元素小，将这个元素赋值给max0跳出循环，如果查找值比列表中的元素小，进行下一次循环。循环结束后，检查max0的值，如果max0为-1，说明待查列表中没有查找值，函数返回-1，如果max0不为-1，继续执行函数。打印块内最大值。对目标块进行线性查找。打印线性查找结果。如果x为-1，函数返回-1，说明没有找到。如果不为-1，返回查找值的位置。
六、哈希查找
代码如下：
maxsize=20
HashTable={i:None for i in range(maxsize)}
print('哈希表大小为%d'%len(HashTable))
def hash(value):
address=value%maxsize
if HashTable[address]==None:
return address
else:
while address
代码输出：
哈希表大小为20
建立键值对(0 20)
建立键值对(10 30)
建立键值对(1 1)
建立键值对(2 2)
建立键值对(5 5)
建立键值对(8 8)
建立键值对(3 23)
建立键值对(4 44)
建立键值对(9 48)
在哈希表里找到44
算法评价：
优点：快！快！快！对列表顺序无要求！。缺点：地址可能会有冲突。占用内存很大。
代码解释：
刚开始学习的时候，我还以为这个算法有多高级，非常的难，其实不就是字典嘛。建立第一个函数： 该函数接收一个值。记录该值的地址为该值对哈希表长度取余的结果。判断在哈希表中该地址对应的值是否存在，如果不存在，返回该地址，如果存在，进行循环，每次对地址加1，再次判断在哈希表中该地址对应的值是否存在，如果不存在，返回该地址，如果存在继续循环，当哈希表地址不够用时，结束循环，函数返回-1。建立第二个函数： 该函数接收一个列表，遍历列表中的每一个元素，记录该元素的地址，打印建立的键值对(键为地址，值为元素)。判断地址是否为-1，如果为-1，说明制定的哈希表长度不够啊，如果不为-1，将键值对放入字典(哈希表)。建立第三个函数： 函数接收构建好了的哈希表和查找值。找到该查找值地址，如果地址冲突，对地址+1，继续循环，直到不会发生冲突，或者，遍历完后没有找到该值。
七、回溯查找
由于篇幅原因，这篇文章不再讲解回溯查找。博主该去吃晚饭了，就到下一篇文章讲解回溯查找吧！要注意身体啊！！！下一篇文章的地址
以上就是本次文章全部内容，非常感谢能够看完的你，如果认为有用或者喜欢的话顺手点个赞吧。
