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

赞 (0)

相关推荐

  • Python二分查找详解

    先来看个实例 #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else: print mid return mid print -1 return -

  • 简介二分查找算法与相关的Python实现示例

    二分查找Binary Search的思想: 以有序表表示静态查找表时,查找函数可以用二分查找来实现. 二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止. 1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n). 假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid  = (low + high) / 2; 具体过程: 1.先将关键字与 mid 指向的元素比较,如果相

  • python实现二分查找算法

    二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[middle]和target进行比较,当它比target小时,那么target一定是在数组的右边,反之,则target在数组的左边,比如它比target小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到target这个数返回或者数组全部遍历完成(target不在数组中) 优

  • Python基于二分查找实现求整数平方根的方法

    本文实例讲述了Python基于二分查找实现求整数平方根的方法.分享给大家供大家参考,具体如下: x=int(raw_input('please input a int:')) if x<0: retrun -1 low=0 high=x ans=(low+high)/2.0 sign=ans while ans**2 !=x: if ans**2>x: high=ans else: low=ans ans=(low+high)/2.0 if sign==ans: break print ans

  • Python实现二分查找与bisect模块详解

    前言 其实Python 的列表(list)内部实现是一个数组,也就是一个线性表.在列表中查找元素可以使用 list.index() 方法,其时间复杂度为O(n) .对于大数据量,则可以用二分查找进行优化. 二分查找要求对象必须有序,其基本原理如下: 1.从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: 2.如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. 3.如果在某一步骤数组为空,则代表找不到. 二分查找也

  • Python实现二分查找算法实例

    本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else:

  • 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 ite

  • python二分法查找算法实现方法【递归与非递归】

    本文实例讲述了python二分法查找算法实现方法.分享给大家供大家参考,具体如下: 二分法查找 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.重复以上过

  • Python递归函数 二分查找算法实现解析

    Python递归函数 二分查找算法实现解析

    一.初始递归 递归函数:在一个函数里在调用这个函数本身. 递归的最大深度:998 正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去.但是我们之前已经说过关于函数调用的问题,每一次函数调用都会产生一个属于它自己的名称空间,如果一直调用下去,就会造成名称空间占用太多内存的问题,于是python为了杜绝此类现象,强制的将递归层数控制在了997(只要997!你买不了吃亏,买不了上当...). 拿什么来证明这个"998理论"呢?这里我们可以做一个实验: def foo(n): pr

  • PHP二分查找算法示例【递归与非递归方法】

    本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9

  • JavaScript使用二分查找算法在数组中查找数据的方法

    本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

  • Python如何实现的二分查找算法

    先来看个用Python实现的二分查找算法实例 import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else: print mid return mid print -1 return -1 if _

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • python快速查找算法应用实例

    本文实例讲述了Python快速查找算法的应用,分享给大家供大家参考. 具体实现方法如下: import random def partition(list_object,start,end): random_choice = start #random.choice(range(start,end+1)) #把这里的start改成random()效率会更高些 x = list_object[random_choice] i = start j = end while True: while li

随机推荐