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

算法是什么?

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

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

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

这就是一种算法。

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

一个程序员应该掌握大概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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏磐创AI技术团队的专栏

快速学习 Python 的全套 14 张思维导图(附高清版下载)

基础知识图一包括了基本规则、Python语言特点、计算机语言、如何运行Python、变量赋值五个方面,辅助你快速掌握Python编程的基底知识。

2433
来自专栏深度学习计算机视觉

算法基础+分治策略(算法复习第1弹)

马上就要算法考试了,好紧张,先复习第一波.... 参考文献(算法导论)+(张莉老师ppt) ---- 函数的增长,对算法效率的描述 渐进记号:Θ、Ω、O、o、...

3287
来自专栏ACM算法日常

海战(线段树)- HDU 4027

这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的...

1042
来自专栏深度学习那些事儿

pytorch新手需要注意的隐晦操作Tensor,max,gather

先看官方的介绍: 如果input是一个n维的tensor,size为 (x0,x1…,xi−1,xi,xi+1,…,xn−1),dim为i,然后index必须...

1.4K8
来自专栏一“技”之长

从一些简单的例子看算法时间复杂度 原

    在编程中,一段代码的执行效率实际上很难估算和预测,其主要受到如下几个方面的影响:

571
来自专栏程序员叨叨叨

6.3 数学操作符(Math Operators)

Cg语言对向量的数学操作提供了内置的支持,Cg中的数学操作符有:*乘法、/除法、-取反、+加法、—减法、%求余、++、——、*=、/=、+=、-=。后面四种运算...

861
来自专栏落影的专栏

程序员进阶之算法练习(十九)

前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

3766
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

4335
来自专栏程序员宝库

用 PHP 的方式实现的各类算法合集

项目地址: https://github.com/PuShaoWei/arithmetic-php About 如果说各种编程语言是程序员的招式,那么数据结构和...

4547
来自专栏落影的专栏

程序员进阶之算法练习(四)

前言 我认为的编程能力: 基础知识:数据库、操作系统、网络原理等; 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)等;...

45410

扫码关注云+社区

领取腾讯云代金券