| 站长开始收学徒,辅导python啦! | 站长答疑 | 本站每日ip已超7000,现出租广告位,位置价格可谈,需要合作请联系站长
+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-04(1)

2019-06(2)

2019-07(2)

2019-08(87)

2019-09(90)

2019-10(11)

2019-11(4)

2019-12(17)

2020-01(27)

2020-02(30)

2020-03(88)

二分查找 & 递归

发布于2020-03-26 11:11     阅读(914)     评论(0)     点赞(1)     收藏(4)


递归

  • 递归条件
    • 自己调用自己
    • 有结束条件
    • 代码
  • 递归优缺点
    • 优点:

      • 递归使代码看起来更加整洁、优雅

      • 可以用递归将复杂任务分解成更简单的子问题

      • 使用递归比使用一些嵌套迭代更容易

    • 缺点:

      • 递归的逻辑很难调试、跟进

      • 递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等

def Afactorial(num):            #定以一个递归函数
   print(num)          #输出当前数字
   if num >0:          #判断当前数字是否>0
      Afactorial(num-1)          # 调用函数本身
   else:
      print('-------')
   print(num)             #再次输出当前数字
Afactorial(3)
#运行结果
3
2
1
0
-------
0
1
2
3

在这里插入图片描述

二分查找

  • 概念
    • 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
  • 查找过程
    • 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,
    • 如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,
    • 如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
    • 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

def binary_search(data_list, target):
    """
    :param data_list: 传入的有序列表
    :param target:  传入要查找的目标值
    """
    low = 0  # 最小数下标
    high = len(data_list) - 1  # 最大数的下标
    index = 1  # 用index来记录查找的次数
 
    while low <= high:
        mid = (low + high) // 2  # 取中间值
 
        if data_list[mid] == target:
            return "一共查找了%d次,此数字在列表中的下标为:%d" % (index, mid)
        elif data_list[mid] > target:
            high = mid - 1  # 如果中间值比目标值大,则在mid左半边找
        else:
            low = mid + 1  # 如果中间值比目标值小,则在mid右半边找
 
        index += 1
    return "一共找了%d次,找不到这样的值!" % index
 
 
ret1 = binary_search(list(range(1, 1000)), 888)
ret2 = binary_search(list(range(1, 1000)), 10000)
print(ret1)
print(ret2)


 #运行结果
一共查找了9次,此数字在列表中的下标为:887
一共找了11次,找不到这样的值!

原文链接:https://blog.csdn.net/Hanmin_hm/article/details/105098849



所属网站分类: 技术文章 > python文章

作者:智慧星辰

链接: https://www.pythonheidong.com/blog/article/285042/

来源:python黑洞网 www.pythonheidong.com

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

1 0

赞一赞 or 踩一踩

收藏该文
已收藏

评论内容:(最多支持255个字符)

最新文章

  day14装饰器

  用python发送邮件(带html格式的邮件、附件)

  小白的pyqt5浏览器

  树莓派4b搭建PyTorch(for buster)

  Python绘制ROC图

  【python3】输出子字符串的最短长度

  使用sorted函数对字典元素排序

  leetcode 1162.地图分析 python BFS 宽度优先搜索

  数据预处理和特征工程

  numpy基础(part5)--卷积

优质资源排行榜

 python经典电子书大合集下载 下载次数 8148

 零基础java开发工程师视频教程全套,基础+进阶+项目实战(152G) 下载次数 7556

 零基础前端开发工程师视频教程全套,基础+进阶+项目实战(共120G) 下载次数 7446

 零基础大数据全套视频400G 下载次数 7009

 零基础php开发工程师视频教程全套,基础+进阶+项目实战(80G) 下载次数 6896

 零基础软件测试全套系统教程 下载次数 6507

 这个项目是人人网的爬虫程序 下载次数 6506

 全套人工智能视频+pdf 下载次数 6446

 IOS全套视频教程 基础班+就业班 下载次数 4681

10  python视频各种视频很多 下载次数 3877

11  编程小白的第一本python入门书(高清版)PDF下载 下载次数 3769

12  effective python编写高质量Python代码的59个有效方法 pdf下载 下载次数 3432

13  Python深度学习 pdf下载 下载次数 3203

14  笨办法学python pdf下载 下载次数 3111

15  Python Cookbook第三版中文PDF下载高清完整扫描原版 下载次数 3045

16  树莓派Python编程指南 pdf下载 下载次数 3029

17  python从入门到精通视频(全60集)python视频教程下载 下载次数 3009

18  Python基础教程 pdf下载 下载次数 3002

19  python项目开发视频 下载次数 3002

20  使用python+pygame开发的小游戏《嗷大喵快跑》源码下载 下载次数 3001

21  黑马2017年java就业班全套视频教程 下载次数 2993

22  Python算法教程_中文版 pdf下载 下载次数 2989

23  python实战项目 平铺图像板系统源码下载,适用于想要保存,标记和共享图像,视频和网页的用户 下载次数 2987

24  利用python实现程序内存监控脚本 下载次数 2987

25  老男孩python自动化视频 下载次数 2983

26  老王python基础+进阶+项目视频教程 下载次数 2975

27  尚硅谷Go学科全套视频 下载次数 2973

28  某硅谷Python项目+AI课程+核心基础视频教程 下载次数 2968

29  Web前端实战精品课程 下载次数 2968

30  tron python小游戏 下载次数 2963

31  [小甲鱼]零基础入门学习Python 下载次数 2962

32  老男孩python全栈开发15期 下载次数 2959

33  2017最新web前端开发完整视频教程附源码 下载次数 2948

34  流畅的Python PDF下载高清完整扫描原版 下载次数 2941

35  Python高性能编程 pdf下载 下载次数 2932

36  最新全套完整JAVAWEB2018开发视频 下载次数 2926

37  Spring boot实战视频6套下载 下载次数 2910

38  python全套视频十五期(116G) 下载次数 2910

39  利用Python进行数据分析 pdf下载 下载次数 2895

40  简明python教程 (A Byte of Python)pdf下载 下载次数 2893

41  Python项目实战 下载次数 2888

42  30个小时搞定Python网络爬虫 含源码 下载次数 2887

43  python全自动抢火车票教程-python视频教程下载 下载次数 2883

44  尚硅谷大数据之Hadoop视频 下载次数 2877

45  python接口测试视频 下载次数 2874

46  Python A~B~C~ python视频教程下载 下载次数 2868

47  全套python量化交易视频教程 下载次数 2866

48  数据结构与算法视频(小甲鱼讲解-全) 下载次数 2864

49  web小程序表白天数倒计时源码下载 下载次数 2863

50  python基础视频教程 下载次数 2862