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

yipeiwu_com6年前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 队列基本定义与使用方法【初始化、赋值、判断等】

python 队列基本定义与使用方法【初始化、赋值、判断等】

本文实例讲述了python 队列基本定义与使用方法。分享给大家供大家参考,具体如下: 队列的特征是:先进先出 应用场景:消息通信、多进程间的协同、多线程间的协同等 在队列中需要设计的实例...

python BlockingScheduler定时任务及其他方式的实现

本文介绍了python BlockingScheduler定时任务及其他方式的实现,具体如下: #BlockingScheduler定时任务 from apscheduler.sc...

django中使用Celery 布式任务队列过程详解

django中使用Celery 布式任务队列过程详解

本文记录django中如何使用celery完成异步任务。 Celery 是一个简单、灵活且可靠的,处理大量消息的分布式系统,并且提供维护这样一个系统的必需工具。 它是一个专注于实时处理的...

python 实现求解字符串集的最长公共前缀方法

问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只...

python重试装饰器的简单实现方法

简单实现了一个在函数执行出现异常时自动重试的装饰器,支持控制最多重试次数,每次重试间隔,每次重试间隔时间递增。 最新的代码可以访问从github上获取 https://github.co...