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 self 参数

1、概述 1.1 场景 我们在使用 Python 中的 方法 method 时,经常会看到 参数中带有 self,但是我们也没对这个参数进行赋值,那么这个参数到底是啥意思呢? 2、知识点...

以一段代码为实例快速入门Python2.7

Python由Guido Van Rossum发明于90年代初期,是目前最流行的编程语言之一,因其语法的清晰简洁我爱上了Python,其代码基本上可以 说是可执行的伪代码。 非常欢迎反馈...

Python 做曲线拟合和求积分的方法

这是一个由加油站油罐传感器测量的油罐高度数据和出油体积,根据体积和高度的倒数,用截面积来描述油罐形状,求出拟合曲线,再用标准数据,求积分来验证拟合曲线效果和误差的一个小项目。 主要的就是...

Python numpy数组转置与轴变换

Python numpy数组转置与轴变换

这篇文章主要介绍了Python numpy数组转置与轴变换,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 矩阵的转置 >&...

python验证码识别教程之滑动验证码

前言 上篇文章记录了2种分割验证码的方法,此外还有一种叫做”滴水算法”(Drop Fall Algorithm)的方法,但本人智商原因看这个算法看的云里雾里的,所以今天记录滑动验证码的处...