1 问题8 u/ b1 T0 U7 N
如何在Python中实现二分查找法的递归？
0 H9 |+ Z9 d& K7 m+ h1 f2 方法/ q( X7 W7 B6 x# l- _* ?; j
二分查找法又称折半查找法，用于预排序列表的查找问题。1 P7 M9 f2 s% } [( T- n
要在排序列表alist中查找元素t，首先，将列表alist中间位置的项与查找关键字t比较，如果两者相等,则查找成功；否则利用中间项将列表分成前、后两个子表，如果中间位置项目大于t，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，即查找成功；或者直到子表不存在为止，即查找不成功。
l: J" n" W% h& C( Y8 |def _binarySearch(key,a,lo,hi):
if hi<=lo:
return -1 #查找失败，返回一1
mid=(lo + hi)//2 #计算中间位置
if a[mid]>key: #中间位置项目大于查找关键字
return_binarySearch(key,a,lo,mid) #递归查找前一子表
elif a[mid]<key: #中间位置项目小于查找关键字
return_binarySearch(key,a,mid+1,hi) #递归查找后一子表
else: #中间位置项目等于查找关键字
return mid #查找成功，返回下标位置
def binarySearch(key,a) #二分查找
return_binarySearch(key,a,0,len(a)) #递归二分查找法
def main():
a=[1,13,26,33,45,55,68,72,83,99]
print("关键字位于列表索引"，binarySearch(33,a))#二分查找关键字33
print("关键字位于列表索引"，binarySearch(58,a))#二分查找关键字58
if__name__=='__main__':main()
3 结语
5 q% x# ]! g h对于如何在Python中实现二分查找法的递归问题，经过测试，是可以实现的，在python中还有很多查找法，比如顺序查找法、冒泡排序法等。 | 
|手机版|小黑屋|paopaomj.COM
( 
渝ICP备18007172号|
渝公网安备50010502503914号 )
发表于 2023-8-7 06:50:30