Python数据结构与算法(18)---检索算法

举报
择城终老 发表于 2021/09/10 23:33:26 2021/09/10
【摘要】 目录 检索算法线性查找图解线性查找实战:线性查找 检索算法 数据结构的排序算法,到17篇归并排序就彻底讲解完成。从今天开始,我们将进入全新的数据结构知识,它的名字叫查找算法,也叫检索...

头图

检索算法

数据结构的排序算法,到17篇归并排序就彻底讲解完成。从今天开始,我们将进入全新的数据结构知识,它的名字叫查找算法,也叫检索算法。

检索算法又分为排序检索与非排序检索。排序检索顾名思义就是先排序在进行查找,在数据库的查找中,我们往往都是这么做的。当然非排序检索也存在,只不过效率非常低。

检索算法包括线性查找、二分查找、插值查找、斐波拉契查找、分块查找、哈希查找以及回溯查找7个算法。所以,从18到24篇都是检索算法的内容知识。

下面,我们来介绍今天第1个要讲解的查找算法:线性查找。

线性查找

线性查找,又名Linear Search,顾名思义就是一种顺序的查找方算法,也是所有查找算法中最简单的一个算法。

其具体的原理:从第1个元素开始依次查找比较,若查找成功,返回其元素的索引;若查找失败,则返回查询无果。

当然,线性查找即可以从数列左边开始,也可以从数列右边开始。同时,它的原始数据既可以是排序好的列表,也可以是非排序列表。

图解线性查找

还是与前面的排序算法一样,我们也将查找算法用图解的方式给大家一一展示出来,这样更方便初学者的理解与学习,具体原理图解图下:

线性查找图解
如上图所示,我们在该列表中查询元素等于3的索引位置。这里,我们从左边i=0开始查找,如果查找成功,则返回对应的索引位置。

实战:线性查找

因为线性查找太过于简单,我们这里实现2中线性查找,一种是从左边开始查找,一种是从右边开始查找。具体示例如下:

# 从左线性查找
def lef_linear_search(my_list, num):
    n = len(my_list)
    i = 0
    while i < n:
        if my_list[i] == num:
            return i
        i += 1
    return "None"
# 从右线性查找
def right_linear_search(my_list, num):
    n = len(my_list)
    i = n - 1
    while i >= 0:
        if my_list[i] == num:
            return i
        i -= 1
    return "None"
if __name__ == "__main__":
    my_list = [8, 0, 4, 3, 2, 1]
    print("线性查找的原始数列:", my_list)
    print("从左边开始线性查找:", lef_linear_search(my_list, 3))
    print("从右边开始线性查找:", lef_linear_search(my_list, 3))

  
 

运行之后,效果如下:

最终结果

文章来源: liyuanjinglyj.blog.csdn.net,作者:李元静,版权归原作者所有,如需转载,请联系作者。

原文链接:liyuanjinglyj.blog.csdn.net/article/details/120104168

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。