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

Myth丶恋晨 2024-03-22 22:15 81阅读 0赞

**1** **问题**

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

**2** **方法**

二分查找法又称折半查找法，用于预排序列表的查找问题。  
要在排序列表alist中查找元素t，首先，将列表alist中间位置的项与查找关键字t比较，如果两者相等,则查找成功；否则利用中间项将列表分成前、后两个子表，如果中间位置项目大于t，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，即查找成功；或者直到子表不存在为止，即查找不成功。

代码清单 1

<table> 
 <tbody> 
  <tr> 
   <td>def&nbsp;_binarySearch(key,a,lo,hi):<br>if hi&lt;=lo:<br>return&nbsp;-1 &nbsp; &nbsp; &nbsp; &nbsp;#查找失败，返回一1<br>mid=(lo&nbsp;+&nbsp;hi)//2 &nbsp;#计算中间位置<br>if a[mid]&gt;key: &nbsp; &nbsp;#中间位置项目大于查找关键字<br>return_binarySearch(key,a,lo,mid) &nbsp; &nbsp;#递归查找前一子表<br>elif a[mid]&lt;key: &nbsp; &nbsp; &nbsp;#中间位置项目小于查找关键字<br>return_binarySearch(key,a,mid+1,hi) &nbsp; &nbsp;#递归查找后一子表<br>else: &nbsp; &nbsp; &nbsp; #中间位置项目等于查找关键字<br>return&nbsp;mid &nbsp; &nbsp; #查找成功，返回下标位置<br>def binarySearch(key,a) &nbsp; &nbsp; #二分查找<br>return_binarySearch(key,a,0,len(a)) &nbsp; &nbsp;#递归二分查找法<br>def main():<br>a=[1,13,26,33,45,55,68,72,83,99]<br>print("关键字位于列表索引"，binarySearch(33,a))#二分查找关键字33<br>print("关键字位于列表索引"，binarySearch(58,a))#二分查找关键字58<br>if__name__=='__main__':main()</td> 
  </tr> 
 </tbody> 
</table>

**3** **结语**

对于如何在Python中实现二分查找法的递的问题，经过测试，是可以实现的，在python中还有很查找法，比如顺序查找法、冒泡排序法等。