python二分查找算法的递归实现方法

335次阅读  |  发布于5年以前

本文实例讲述了python二分查找算法的递归实现方法。分享给大家供大家参考,具体如下:

这里先提供一段二分查找的代码:


    def binarySearch(alist, item):
      first = 0
      last =
    len(alist)-1
      found = False
      while first<=last
    and not found:
    midpoint = (first + last)//2
    if alist[midpoint] == item:
       found = True
    else:
       if item < alist[midpoint]:
      last = midpoint-1
       else:
      first = midpoint+1
      return found
    testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
    print(binarySearch(testlist, 3))
    print(binarySearch(testlist, 13))

近来喜欢递归的简单明了,所以修改成递归的方法:


    def binSearch(lst, item):
      mid = len(lst) //2
      found = False
      if lst[mid] ==
    item:
     found = True
     return found
      if mid == 0:
    #mid等于0就是找到最后一个元素了。
     found = False
     return found
      else:
     if item > lst[mid]: #找后半部分
       #print(lst[mid:])
       return
    binSearch(lst[mid:], item)
     else:
       return
    binSearch(lst[:mid], item) #找前半部分

测试通过。

更多关于Python相关内容可查看本站专题:《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8