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

yipeiwu_com5年前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开发之for循环操作实例详解

本文实例讲述了python开发之for循环操作。分享给大家供大家参考,具体如下: 下面是我做的一些学习记录供大家参考: #基本的for循环语句 test_list = [2,"Jon...

python+rsync精确同步指定格式文件

本文实例为大家分享了python+rsync精确同步指定格式文件的具体代码,供大家参考,具体内容如下 # coding: utf-8 #!/usr/bin/env python '...

Python实现随机漫步功能

Python实现随机漫步功能

随机漫步生成是无规则的,是系统自行选择的结果。根据设定的规则自定生成,上下左右的方位,每次所经过的方向路径。 首先,创建一个RandomWalk()类和fill_walk()函数 ran...

对python-3-print重定向输出的几种方法总结

方法1: import sys f=open('test.txt','a+') a='123' b='456' print >> f,a,b f.close...

Tornado协程在python2.7如何返回值(实现方法)

错误写法 class RemoteHandler(web.RequestHandler): @gen.coroutine def get(self): resp...