在Python中实现二分查找法的递归

admin

1 问题
如何在Python中实现二分查找法的递归？
- O. A9 S  D" A& A8 g8 D2 方法
二分查找法又称折半查找法，用于预排序列表的查找问题。
要在排序列表alist中查找元素t，首先，将列表alist中间位置的项与查找关键字t比较，如果两者相等,则查找成功；否则利用中间项将列表分成前、后两个子表，如果中间位置项目大于t，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，即查找成功；或者直到子表不存在为止，即查找不成功。
4 G( l: ?3 v+ X1 n( N& o

复制代码
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 结语
对于如何在Python中实现二分查找法的递归问题，经过测试，是可以实现的，在python中还有很多查找法，比如顺序查找法、冒泡排序法等。