python二分查找算法的递归实现方法
本文实例讲述了python二分查找算法的递归实现方法。分享给大家供大家参考,具体如下:
这里先提供一段二分查找的代码:
defbinarySearch(alist,item): first=0 last= len(alist)-1 found=False whilefirst<=last andnotfound: midpoint=(first+last)//2 ifalist[midpoint]==item: found=True else: ifitem<alist[midpoint]: last=midpoint-1 else: first=midpoint+1 returnfound testlist=[0,1,2,8,13,17,19,32,42,] print(binarySearch(testlist,3)) print(binarySearch(testlist,13))
近来喜欢递归的简单明了,所以修改成递归的方法:
defbinSearch(lst,item): mid=len(lst)//2 found=False iflst[mid]== item: found=True returnfound ifmid==0: #mid等于0就是找到最后一个元素了。 found=False returnfound else: ifitem>lst[mid]:#找后半部分 #print(lst[mid:]) return binSearch(lst[mid:],item) else: return binSearch(lst[:mid],item)#找前半部分
测试通过。
更多关于Python相关内容可查看本站专题:《Python正则表达式用法总结》、《Python数据结构与算法教程》、《PythonSocket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。