Python查找算法如何实现

第Python查找算法如何实现print(pos)

通过前面对二分算法流程的分析，可知二分查找的子问题和原始问题是同一个逻辑，所以可以使用递归实现：

递归实现二分查找

defbinary_find_dg(nums,key,l_idx,r_ldx):

ifl_idxr_ldx:

#出口一：没有查找到给定关键字

return-1

#计算出中间位置

mid_pos=(r_ldx+l_idx)//2

#计算中间位置的值

mid_val=nums[mid_pos]

#与关键字比较

ifmid_val==key:

#出口二：比较相等，有此关键字，返回关键字所在位置

returnmid_pos

elifmid_valkey:

#说明查找范围应该缩少在原数的左边

r_ldx=mid_pos-1

else:

l_idx=mid_pos+1

returnbinary_find_dg(nums,key,l_idx,r_ldx)

测试二分查找

if__name__==__main__:

nums=[1,3,4,5,8,10,12]

key=8

pos=binary_find_dg(nums,key,0,len(nums)-1)

print(pos)

二分查找性能分析：

二分查找的过程用树形结构描述会更直观，当搜索完毕后，绘制出来树结构是一棵二叉树。

1.如上述代码执行过程中，先找到数列中的中间数字5，然后以5为根节点构建唯一结点树。

2.5和关键字8比较后，再在以数字5为分界线的右边数列中找到中间数字10，树形结构会变成下图所示。

3.10和关键字8比较后，再在10的左边查找。

查找到8后，意味着二分查找已经找到结果，只需要3次就能查找到最终结果。

从二叉树的结构上可以直观得到结论：二分查找关键字的次数由关键字在二叉树结构中的深度决定。

4.上述是查找给定的数字8，为了能查找到数列中的任意一个数字，最终完整的树结构应该如下图所示。

很明显，树结构是标准的二叉树。从树结构上可以看出，无论查找任何数字，最小是1次，如查找数字5，最多也只需要3次，比线性查找要快很多。

根据二叉树的特性，结点个数为n的树的深度为h=log2(n+1)，所以二分查找算法的大O表示的时间复杂度为O(logn)，是对数级别的时间度。

当对长度为1000的数列进行二分查找时，所需次数最多只要10次，二分查找算法的效率显然是高效的。

然而，二分查找算法在实行之前需要对数列进行排序，因此前面所述的时间复杂度并未包含排序所需的时间。所以，二分查找一般适合数字变化稳定的有序数列。

3.插值查找

插值查找本质是二分查找，插值查找对二分查找算法中查找中间位置的计算逻辑进行了改进。

原生二分查找算法中计算中间位置的逻辑：中间位置等于左指针位置加上右指针位置然后除以2。

#计算中间位置

mid_pos=(r_ldx+l_idx)//2

插值算法计算中间位置逻辑如下所示：

key为要查找的关键字！！

#插值算法中计算中间位置

mid_pos=l_idx+(key-nums[l_idx])//(nums[r_idx]-nums[l_idx])*(r_idx-l_idx)

编码实现插值查找：

#插值查找基于二分法，只是mid计算方法不同

defbinary_search(nums,key):

l_idx=0

r_idx=len(nums)-1

old_mid=-1

mid_pos=None

whilel_idxr_idxandnums[0]=keyandnums[r_idx]=keyandold_mid!=mid_pos:

#中间位置计算

mid_pos=l_idx+(key-nums[l_idx])//(nums[r_idx]-nums[l_idx])*(r_idx-l_idx)

old_mid=mid_pos

ifnums[mid_pos]==key:

returnindexis{},targetvalueis{}.format(mid_pos,nums[mid_pos])

#此时目标值在中间值右边，更新左边界位置

elifnums[mid_pos]key:

l_idx=mid_pos+1

#此时目标值在中间值左边，更新右边界位置

elifnums[mid_pos]key:

r_idx=mid_pos-1

returnNotfind

li=[1,3,4,5,8,10,12]

print(binary_search(li,6))

插值算法的中间位置计算时，对中间位置的计算有可能多次计算的结果是一样的，此时可以认为查找失败。

插值算法的性能介于线性查找和二分查找之间。

如果序列具有较大数量的均匀分布的数字，插值查找算法的平均执行效率要比二分查找好得多。如果数据在数列中分布不均匀，插值算法并不是最优选择。

4.分块查找

分块查找类似于数据库中的索引查询，所以分块查找也称为索引查找。其算法的核心还是线性查找。

现有原始数列nums=[5,1,9,11,23,16,12,18,24,32,29,25]，需要查找关键字11是否存在。

第1步：使用分块查找之前，先要对原始数列按区域分成多个块。至于分成多少块，可根据实际情况自行定义。分块时有一个要求，前一个块中的最大值必须小于后一个块的最小值。

块内部无序，但要保持整个数列按块有序。

分块查找要求原始数列从整体上具有升序或降序趋势，如果数列的分布不具有趋向性，如果仍然想使用分块查找，则需要进行分块有序调整。

第2步：根据分块信息，建立索引表。索引表至少应该有2个字段，每一块中的最大值数字以及每一块的起始地址。显然索引表中的数字是有序的。

第3步：查找给定关键字时，先查找索引表，查询关键字应该在那个块中。如查询关键字29，可知应该在第三块中，然后根据索引表中所提供的第三块的地址信息，再进入第三块数列，按线性匹配算法查找29具体位置。

编码实现分块查找：

先编码实现根据分块数量、创建索引表，这里使用二维列表保存储索引表中的信息。

分块：建立索引表

nums原始数列

blocks块大小

defcreate_index_table(nums,blocks):

#索引表使用列表保存

index_table=[]

#每一块的数量

n=len(nums)//blocks

foriinrange(0,len(nums),n):

#索引表中的每一行记录

tmp_lst=[]

#最大值

tmp_lst.append(max(nums[i:i+n-1]))

#起始地址

tmp_lst.append(i)

#终止地址

tmp_lst.append(i+n-1)

#添加到索引表中

index_table.append(tmp_lst)

returnindex_table

nums=[5,1,9,11,23,16,12,18,24,32,29,25]

it=create_index_table(nums,3)

print(it)

输出结果：

[[11,0,3],[23,4,7],[32,8,11]]

代码执行后，输出结果和分析的结果一样。

以上代码仅对整体趋势有序的数列进行分块。如果整体没有向有序趋势发展，则需要提供适当的块排序计划，有兴趣的人可以自行完成。

如上代码仅为说明分块查找算法。

分块查找的完整代码：

分块：建立索引表

nums原始数列

blocks块大小

defcreate_index_table(nums,blocks):

#索引表使用列表保存

index_table=[]

#每一块的数量

n=len(nums)//blocks