溪明轩

  • Python全栈开发
  • 三溪杂选
  • 爬虫快速入门
  • 首页
  • 文章归档
  • 关于页面

  • 搜索
consul ELK Loki M3DB Thanos TSDB federate ALertmanager PromQL Grafana prometheus nginx Rest Framework 热视图 ansible 网络安全 云盘 wiki Python 爬虫

19、Python算法之二分法

发表于 2020-12-05 | 分类于 Python函数 | 0 | 阅读次数 165

算法,即高效解决问题的方法!比如我晚上下班回去需要煮饭炒菜煲药,如果不考虑效率问题,那么煮完饭再炒菜然后煲药也是可以的,但是这种方式明显效率低下!如何提升效率呢?先来分析一下:煮饭和煲药都是需要一定时间的,而且开火后一段时间内都不需要管理,那么我可以先煮饭、煲药,在等它们完成的这段时间内,我可以备菜并进行烹饪,这样就大大提升了效率!

二分法是一种基础算法,顾名思义,把一个整体切分成两部分来进行比较,前提是有序的数据类型!下面来一个例子吧!

假设现在有一个按照从小到大的顺序来排列的列表,我需要从中找到想要的那个数字,如何做到?

先来展示不考虑算法的做法,为了更便于理解,每一次for循环都打印一次值!

l3 = [1, 3, 6, 8, 12, 24, 37, 46, 58, 66, 71, 83, 95]
lucky_number = 95
for number in l3:
    print(number)
    if lucky_number == number:
        print('we found lucky_number:', lucky_number)
        
# 执行得到结果,可以看到,因为要取的值正好在末尾,因此要遍历整个列表!
1
3
6
8
12
24
37
46
58
66
71
83
95
we found lucky_number: 95

使用二分法思路来解决这个问题

l3 = [1, 3, 6, 8, 12, 24, 37, 46, 58, 66, 71, 83, 95]

def half_algo(lucky_number, your_list):
    print(your_list)
    middle_index = len(your_list) // 2  # 取索引的中间值
    if lucky_number > your_list[middle_index]:
        your_list = your_list[middle_index + 1:]  # 因中间的索引对应的元素已经比较过,所以索引要+1往后算,:是切片意思
        half_algo(lucky_number, your_list)  # 函数递归

    elif lucky_number < your_list[middle_index]:
        your_list = your_list[:middle_index - 1]
        half_algo(lucky_number, your_list)

    else:
        print('we found lucky_number:', lucky_number)

half_algo(95, l3)

# 执行得到结果,可以看到,仅循环了三次就取到了值!
[1, 3, 6, 8, 12, 24, 37, 46, 58, 66, 71, 83, 95]
[46, 58, 66, 71, 83, 95]
[83, 95]
we found lucky_number: 95
Donate comment here
三溪 微信支付

微信支付

三溪 支付宝

支付宝

  • 本文作者: 三溪
  • 本文链接: https://blog.sanxi.info/archives/1-9--p-y-t-h-o-n-suan-fa-zhi-er-fen-fa
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-ND 4.0 许可协议。转载请注明出处!
18、Python之函数递归
20、初识面向过程与函数式编程
  • 文章目录
  • 站点概览
三溪

三溪

作诗不作法

120 日志
23 分类
20 标签
RSS
Creative Commons
Links
  • halo官网
  • 玻璃之空
0%
© 2022 三溪
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
世间微尘里 独爱茶酒中