当前位置:主页 > python教程 > Python递归函数 二分查找算法实现解析

基于Python递归函数实现二分查找算法

发布:2020-01-23 10:53:40 119


给网友们整理Python相关的编程文章,网友富欣荣根据主题投稿了本篇教程内容,涉及到python、递归函数、二分查找算法、Python递归函数 二分查找算法实现解析相关内容,已被757网友关注,如果对知识点想更进一步了解可以在下方电子资料中获取。

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

一、初始递归

递归函数:在一个函数里在调用这个函数本身。

递归的最大深度:998

正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去。但是我们之前已经说过关于函数调用的问题,每一次函数调用都会产生一个属于它自己的名称空间,如果一直调用下去,就会造成名称空间占用太多内存的问题,于是python为了杜绝此类现象,强制的将递归层数控制在了997(只要997!你买不了吃亏,买不了上当...).

拿什么来证明这个“998理论”呢?这里我们可以做一个实验:

def foo(n):
  print(n)
  n += 1
  foo(n)
foo(1)

由此我们可以看出,未报错之前能看到的最大数字就是998.当然了,997是python为了我们程序的内存优化所设定的一个默认值,我们当然还可以通过一些手段去修改它:

import sys
print(sys.setrecursionlimit(100000))

我们可以通过这种方式来修改递归的最大深度,刚刚我们将python允许的递归深度设置为了10w,至于实际可以达到的深度就取决于计算机的性能了。不过我们还是不推荐修改这个默认的递归深度,因为如果用997层递归都没有解决的问题要么是不适合使用递归来解决要么是你代码写的太烂了~~~

看到这里,你可能会觉得递归也并不是多么好的东西,不如while True好用呢!然而,江湖上流传这这样一句话叫做:人理解循环,神理解递归。所以你可别小看了递归函数,很多人被拦在大神的门槛外这么多年,就是因为没能领悟递归的真谛。而且之后我们学习的很多算法都会和递归有关系。来吧,只有学会了才有资本嫌弃!

二、递归示例讲解

这里我们又要举个例子来说明递归能做的事情。

例一:

现在你们问我,alex老师多大了?我说我不告诉你,但alex比 egon 大两岁。

你想知道alex多大,你是不是还得去问egon?egon说,我也不告诉你,但我比武sir大两岁。

你又问武sir,武sir也不告诉你,他说他比太白大两岁。

那你问太白,太白告诉你,他18了。

这个时候你是不是就知道了?alex多大?

 

1 金鑫 18
2 武sir 20
3 egon 22
4 alex 24

 

你为什么能知道的?

首先,你是不是问alex的年龄,结果又找到egon、武sir、太白,你挨个儿问过去,一直到拿到一个确切的答案,然后顺着这条线再找回来,才得到最终alex的年龄。这个过程已经非常接近递归的思想。我们就来具体的我分析一下,这几个人之间的规律。

age(4) = age(3) + 2 
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 40

那这样的情况,我们的函数怎么写呢?

def age(n):
  if n == 1:
    return 40
  else:
    return age(n-1)+2
print(age(4))

如果有这样一个列表,让你从这个列表中找到66的位置,你要怎么做?

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

你说,so easy!

l.index(66)...

我们之所以用index方法可以找到,是因为python帮我们实现了查找方法。如果,index方法不给你用了。。。你还能找到这个66么?

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
i = 0
for num in l:
  if num == 66:
    print(i)
  i+=1

上面这个方法就实现了从一个列表中找到66所在的位置了。

但我们现在是怎么找到这个数的呀?是不是循环这个列表,一个一个的找的呀?假如我们这个列表特别长,里面好好几十万个数,那我们找一个数如果运气不好的话是不是要对比十几万次?这样效率太低了,我们得想一个新办法。

二分查找算法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

你观察这个列表,这是不是一个从小到大排序的有序列表呀?

如果这样,假如我要找的数比列表中间的数还大,是不是我直接在列表的后半边找就行了?

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

这就是二分查找算法!

那么落实到代码上我们应该怎么实现呢?

简单版二分法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def func(l,aim):
  mid = (len(l)-1)//2
  if l:
    if aim > l[mid]:
      func(l[mid+1:],aim)
    elif aim < l[mid]:
      func(l[:mid],aim)
    elif aim == l[mid]:
      print("bingo",mid)
  else:
    print('找不到')
func(l,66)
func(l,6)

升级版二分法

l1 = [1, 2, 4, 5, 7, 9]
def two_search(l,aim,start=0,end=None):
  end = len(l)-1 if end is None else end
  mid_index = (end - start) // 2 + start
  if end >= start:
    if aim > l[mid_index]:
      return two_search(l,aim,start=mid_index+1,end=end)
    elif aim < l[mid_index]:
      return two_search(l,aim,start=start,end=mid_index-1)

    elif aim == l[mid_index]:
      return mid_index
    else:
      return '没有此值'
  else:
    return '没有此值'
print(two_search(l1,9))

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。


参考资料

相关文章

  • python切片操作的知识点总结

    发布:2019-11-02

    切片操作基本表达式:object[start_index :end_index:step]。一个完整的切片表达式包含两个“:”,用于分隔三个参数,当只有一个“:”时,默认第三个参数step=1。


  • Python 稀疏矩阵中sparse存储和转换实例讲解

    发布:2021-04-27

    这篇文章主要介绍了Python 稀疏矩阵-sparse 存储和转换的相关资料,需要的朋友可以参考下


  • python将bmp转换为jpg格式并删除原图的具体操作

    发布:2019-07-30

    今天小编就为大家分享一篇python bmp转换为jpg 并删除原图的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧


  • python数据封装json格式数据的实例方法

    发布:2019-08-30

    本次内容是小编在网上整理的关于如何python数据封装json格式的内容总结,有兴趣的读者们参考下。


  • python命令行参数argparse模块基本用法详解

    发布:2023-04-27

    argparse 是python自带的命令行参数解析包,可以用来方便地读取命令行参数,这篇文章主要介绍了python命令行参数-argparse模块基本用法,需要的朋友可以参考下


  • Python配置mysql的详细步骤方法

    发布:2020-05-28

    下面小编就为大家带来一篇Python配置mysql的教程(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧


  • Python读取xlsx数据生成图标代码实例

    发布:2021-05-09

    这篇文章主要介绍了Python读取xlsx数据生成图标代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下


  • Python基于TensorFlow接口实现深度学习神经网络回归

    发布:2023-04-06

    这篇文章主要为大家详细介绍了如何基于Python语言中TensorFlow的tf.estimator接口,实现深度学习神经网络回归的具体方法,感兴趣的可以了解一下


网友讨论