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

yipeiwu_com7年前Python基础

本文实例讲述了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程序设计有所帮助。

相关文章

python对excel文档去重及求和的实例

废话不多说,估计只有我这个菜鸟废了2个小时才搞出来,主要是我想了太多方法来实现,最后都因为这因为那的原因失败了 间接说明自己对可变与不可变类型的了解,还是不够透彻 最后就用了个笨方法解决...

浅析Python函数式编程

Functional Programming,函数式编程。Python对函数式编程提供部分支持。对于纯函数编程,对任一函数,只要输入是确定的,输出就是确定的,可称之为无副作用。 一、高阶...

Django admin美化插件suit使用示例

Django admin美化插件suit使用示例

本文主要对Django美化插件做一个简单介绍,具体如下。 Django Suit 效果 使用前django页面 使用后django页面 安装 官方文档 http://django-s...

深入理解python中函数传递参数是值传递还是引用传递

目前网络上大部分博客的结论都是这样的: Python不允许程序员选择采用传值还是传 引用。Python参数传递采用的肯定是“传对象引用”的方式。实际上,这种方式相当于传值和传引用的一种综...

Python中atexit模块的基本使用示例

Python中atexit模块的基本使用示例

atexit模块很简单,只定义了一个register函数用于注册程序退出时的回调函数,我们可以在这个回调函数中做一些资源清理的操作。 注:如果程序是非正常crash,或者通过os._ex...