专栏首页一个爱吃西瓜的程序员每天学习一点儿算法--二分查找

每天学习一点儿算法--二分查找

算法是什么?

算法就是完成一组特定任务的方法。

比如将大象放进冰箱需要三步:

  • 打开冰箱
  • 将大象放进冰箱
  • 关闭冰箱

这就是一种算法。

如果用计算机语言来叙述,就是任何实现某种功能的代码片段都可以称之为算法。

一个程序员应该掌握大概50种基本算法,但目前我们属于初级阶段,先掌握一些简单有趣的算法,为日后进一步的算法学习打下基础。

二分查找

比如我要在字典(这里是真实的字典,不是Python的dict类型)中查找以O为拼音首字母的汉字,我会从字典的中间附近开始翻阅,因为我知道字母O在26个字母的中间附近,这会提高我的查找效率。在这里,我就运用了二分查找的思想。

二分查找是一种算法,它的思想就是:

1.在一个有序的元素列表中,每次将查找的元素与元素列表的中间元素作比较

2.如果等于中间元素,则查找完毕

3.若比中间元素大,则在大于中间元素的一半中重复步骤1

4.若比中间元素小,则在小于中间元素的一半中重复步骤1

5.重复步骤2或3或4,直至查找完毕

注释:仅当列表是有序的时候,二分查找才管用。

一般而言,对于包含n个元素的有序列表,用二分查找最多需要㏒₂n步,而简单查找最多需要n步。

我们一般使用大O表示法来表征算法的运行时间,其中㏒一般指的是㏒₂

现在我们来看看如何使用Python来编写二分查找的代码,这里以一个简单的数组示例:

def binary_search(list, item):    """定义一个二分查找的函数"""
    # low 和 high用于跟踪要在其中查找的列表部分
    low = 0
    high = len(list) - 1

    while low <= high:        global n
        mid = int((low + high)/2)  # 检查中间的元素
        guess = list[mid]
        n = n + 1  # 时间复杂度计数

        if guess == item:            # 找到了元素
            return mid        elif guess > item:            # 猜的数大了
            high = mid - 1
        else:            # 猜的数小了
            low = mid + 1
    return None  # 没有查询到指定的元素

n = 0
my_list = [1, 3, 5, 7, 9, 10]
result = binary_search(my_list, 7)  # 指定元素的位置

print("查询结果:", result)
print("时间复杂度:", n)

执行结果:

查询结果: 3
时间复杂度: 3

需要说明的是,二分查找的查询结果是返回待查找元素在列表中的位置,当然,列表是以0开始标记的。

大O表示法

大O表示法是一种特殊的表示法, 它指出了算法的运行速度有多快。例如,假设列表包含n个元素,简单查找需要检查每个元素,因此需要执行n次操作,使用大O表示法,它的运行时间为O(n),它的单位是秒么?不是,它没有单位。

大O表示法指的并非以秒为单位的速度。它指的是算法运行时间的增速(强调增速)。

比如,为检查长度为n的列表,二分查找需要执行㏒n次操作。使用大O表示法,它的运行时间为O(㏒n)。

我们来对比一下简单查找和二分查找的增速差异(假设检查一个元素需要1毫秒):

这里就能看出两者运行时间的增速有着天壤之别

大O表示法指出的是平均情况下的运行时间

比如,简单查找的运行时间用大O表示法是O(n),但是如果列表的第一个元素就是待查找元素,那么简单查找的运行时间就是O(1)。但这只是特殊情况,一般而言,简单查找的运行时间是O(n)。

一些常见的大O运行时间

下面从快到慢列举了5种常见的大O运行时间

  • O(㏒ n), 也叫对数时间,这样的算法包括二分查找
  • O(n), 也叫线性时间,这样的算法包括简单查找
  • O(n*㏒n), 这样的算法包括快速排序—一种速度较快的排序算法
  • O(n²), 这样的算法包括选择排序—一种速度较慢的排序算法
  • O(n!), 这样的算法包括旅行商问题的解决方案—一种非常慢的算法

旅行商问题

旅行商问题是计算机科学领域一个十分著名的问题。这个问题是怎样的呢?

有一位旅行商,他要前往5个城市。

画的图好丑

同时要确保旅程最短。为此,可以考虑去往这些城市的各种可能顺序。高中学过的排列组合的知识告诉我们,5个城市有120种不同组合。因此,在涉及5个城市时,需要执行120次操作。涉及6个城市时,需要执行720次操作。

推而广之,涉及n个城市时,需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间为O(n!),即阶乘时间。在涉及的城市较多时,这个算法根本无法在有效的时间内计算出结果。面对这种问题,我们只能去找出近似答案~

小结

  • 二分查找的速度比简单查找快得多
  • 算法的运行时间不是以秒为单位的
  • 算法的运行时间是从其增速的角度衡量的
  • 算法的运行时间使用大O表示法表示

每天学习一点点,每天进步一点点。

本文分享自微信公众号 - 小白客(youcoding),作者:爱吃西瓜的番茄酱

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一些关于Git的学习资源

    Git是什么? Git是目前这个星球上最厉害的分布式版本控制系统。 Git有什么特点? 一句话描述:只要你用过它,你就一定会爱上它的,而且是爱不释手的那种,因...

    爱吃西瓜的番茄酱
  • 如何霸占跳一跳好友排行榜第一?

    由于这款游戏耐玩性、有趣性很高,拥有免下载安装,用完即走的强大特性。最重要的是可以实时好友排名,因此在诞生的短短几日里就风靡朋友圈。 看着好友排名里面一个比一个...

    爱吃西瓜的番茄酱
  • 分享一波 Spring Boot 学习资源

    Spring Boot 是一款 Java 平台的开源框架,它基于 Spring4.0 设计,其设计目的是用来简化新 Spring 应用的初始搭建以及开发过程。

    爱吃西瓜的番茄酱
  • 【从0到1学算法】二分查找法

    说到算法,大家应该都会脑壳疼吧。除了应付一下面试,准备过算法,也接触过不少算法,但是面试完了,基本上就忘光了。但不得不说,算法真的很重要,算法是解决问的方法,你...

    KEN DO EVERTHING
  • 铲屎官们千万别点!这个小程序,有毒

    而这个单纯的小程序只有一个目的,就是让你尽情地看猫,每天不看个 100 来遍都停不下来的那种。

    知晓君
  • 为什么软件总是不靠谱

    本文作者:张海龙,CODING 创始人兼 CEO。技术创业者,十多年来一直在技术圈、开发工具领域耕耘, 2014 年创办 CODING ,给企业用户全套 Dev...

    CODING
  • 日常评 | 深夜,来谈一谈未来 #191005

    假期已经过半,近期对于未来的科技发展,有些许想法从头脑中迸出。趁着假期这个机会分享给大家。

    ZNing
  • WSL权限管理

    WSL (Win­dows Sub­sys­tem for Linux) 通过 /mnt 目录下的 c、d、e 等目录可分别访问本地的 C、D、E 等盘,虽然可...

    happy123.me
  • 为什么SD-WAN现在飞速发展?

    现在将不再是这种情况。现在,SD-WAN市场使用网络虚拟化来利用、管理和保护互联网宽带,为企业应用构建更强大的网络,SD-WAN正在蓬勃发展,并有望达到数十亿美...

    SDNLAB
  • 什么是CI/CD,你了解它给团队带来的收益和挑战吗?

    CI/CD 的出现改变了开发人员和测试人员发布软件的方式。本文是描述这一变化的系列文章第一篇, 这些文章将提供各种工具和流程的讲解,以帮助开发人员更好的使用 C...

    灵雀云

扫码关注云+社区

领取腾讯云代金券