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程序设计有所帮助。

相关文章

对pandas通过索引提取dataframe的行方法详解

对pandas通过索引提取dataframe的行方法详解

一、假设有这样一个原始dataframe 二、提取索引 (已经做了一些操作将Age为NaN的行提取出来并合并为一个dataframe,这里提取的是该dataframe的索引,道理和操作...

django 按时间范围查询数据库实例代码

从前台中获得时间范围,在django后台处理request中数据,完成format,按照范围调用函数查询数据库。 介绍一个简单的功能,就是从web表单里获取用户指定的时间范围,然后在数据...

Python3 利用requests 库进行post携带账号密码请求数据的方法

如下所示: import urllib,json,requests url = 'http://127.0.0.1:8000/account/login' headers = {}...

python的turtle库使用详解

python的turtle库使用详解

python中的turtle库是3.6版本中新推出的绘图工具库,那么如何使用呢?下面小编给大家分享一下。 首先打开pycharm软件,右键单击选择新建一个python file 接下来...

Python实现统计英文单词个数及字符串分割代码

Python实现统计英文单词个数及字符串分割代码

字符串分割 复制代码 代码如下: str="a|and|hello|||ab" alist = str.split('|') print alist 结果 复制代码 代码如下: st...