【Python数据结构与算法】—— 搜索算法 | 期末复习不挂科系列

本文主要是介绍【Python数据结构与算法】—— 搜索算法 | 期末复习不挂科系列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

🌈个人主页: Aileen_0v0
🔥系列专栏: 数据结构与算法
💫个人格言:"没有罗马,那就自己创造罗马~"


这篇博客主要探索的是计算机科学常见问题---搜索算法

“时间紧,任务重!”

话不多说,开始今天的学习之旅吧⛵~


目录

搜索

定义

关键字-in

顺序搜索 

无序表的顺序搜索过程

无序表的顺序搜索代码实现 

分析顺序搜索算法

有序列表

有序列表的顺序搜索过程​编辑

无序表的顺序搜索代码实现 


搜索

定义

搜索是指从元素集合中找到特定元素算法过程

搜索过程通常返回True 或 False 来表示元素是否在集合中。

有时也可以修改搜索过程,使它返回目标元素的位置。

为了更好的打好算法基础,我们这次先探索搜索的元素是否存在这一问题。


关键字-in

in是Python中的关键字,用于判断一个元素是否存在于一个容器中。可以用于列表、元组、字典、集合等数据类型。它可以被用于for循环语句 和 if语句中。

我们之前做Python每日一练时我曾科普过Python中 我们可以通过运算符 —— in 去检查元素是否在列表中。

print(15 in [1,2,3])
print(15 in [1,2,3,15])

运行结果: 


顺序搜索 

线性结构(数组、链表、栈、队列等)都有下标。每个数据项都有一个相对于其它数据项的位置。

Python的列表 ,数据项的位置就是其下标。

因为下标有序的,So 我们能够进行 顺序访问顺序搜索

无序表的顺序搜索过程

下图展示了顺序搜索的过程。

无序表的顺序搜索代码实现 

def sequential_search(a_list,item):pos = 0while pos < len(a_list):if a_list[pos] == item:return  Truepos += 1return  Falseprint(sequential_search([1,2,4,5,9],5))

从列表第一个元素开始, 沿着下表顺序逐个查看,直到找到目标元素或者到达列表末尾。

若查完列表后仍未找到目标元素,则说明目标元素不在列表中。

分析顺序搜索算法

分析搜索算法前,首先需要先定义 计算的基本单元---解决问题过程中不断重复的的某一步

对搜索来说,记录 比较的次数 是合理的 性能指标。

每次比较只有两个结果: 找到目标元素,或未找到。

假设元素排列无序,则目标元素在每一个位置出现的可能都相同。

确定目标元素是否在列表中,唯一的方法就是将它与列表中的每个元素都比较一次

列表中有n个元素,那么顺序搜索经过 n 次比较后才能确定目标元素不在列表中。如果列表含目标元素,分析起来更复杂。实际上有 3 种可能的情况:

最好情况目标元素位于列表的第一个位置,则只需比较一次;

最坏情况目标元素位于最后一个位置,则需要比较 n次

平均情况目标元素位于中间位置,则需要比较 n / 2次。 --> 当n增大,系数则可省略,所以顺序搜索时间复杂度O(n)


有序列表

有序列表的顺序搜索过程

通过观察上图有序列表列表中的顺序搜索过程我们可以得出以下结论:

元素按升序排列

如果存在目标元素,那么它出现在 n个位置中任意一个位置的可能性仍然一样大,因此比较次数与在无序列表相同

But,如果不存在目标元素,那么搜索效率就会提高。---> 因为当找到比目标元素大的数的时候程序就会停止搜索

无序表的顺序搜索代码实现 

#有序表的顺序搜索
def ordered_sequential_search(a_list,item):pos = 0while pos < len(a_list):if a_list[pos] == item:return Trueelif a_list[pos] > item:return Falsepos += 1return False
print(ordered_sequential_search([1,2,4,5,9],6))

下表总结了,在有序表中搜索时的比较次数。

最好情况:只需比较1次。  平均情况比较 n / 2 次,但时间复杂度仍是O(n)。

总结:只有当列表不存在目标元素时,有序排列的元素,才能提高顺序搜索的效率

📝总结:

本篇文章介绍了搜索算法以及,有序列表在搜索算法中 的优势,前提条件是:只有当元素不在列表中时有序排列的元素,才能提高顺序搜索的效率

这篇关于【Python数据结构与算法】—— 搜索算法 | 期末复习不挂科系列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/476931

相关文章

VSCode配置Anaconda Python环境的实现

《VSCode配置AnacondaPython环境的实现》VisualStudioCode中可以使用Anaconda环境进行Python开发,本文主要介绍了VSCode配置AnacondaPytho... 目录前言一、安装 Visual Studio Code 和 Anaconda二、创建或激活 conda

pytorch+torchvision+python版本对应及环境安装

《pytorch+torchvision+python版本对应及环境安装》本文主要介绍了pytorch+torchvision+python版本对应及环境安装,安装过程中需要注意Numpy版本的降级,... 目录一、版本对应二、安装命令(pip)1. 版本2. 安装全过程3. 命令相关解释参考文章一、版本对

讯飞webapi语音识别接口调用示例代码(python)

《讯飞webapi语音识别接口调用示例代码(python)》:本文主要介绍如何使用Python3调用讯飞WebAPI语音识别接口,重点解决了在处理语音识别结果时判断是否为最后一帧的问题,通过运行代... 目录前言一、环境二、引入库三、代码实例四、运行结果五、总结前言基于python3 讯飞webAPI语音

基于Python开发PDF转PNG的可视化工具

《基于Python开发PDF转PNG的可视化工具》在数字文档处理领域,PDF到图像格式的转换是常见需求,本文介绍如何利用Python的PyMuPDF库和Tkinter框架开发一个带图形界面的PDF转P... 目录一、引言二、功能特性三、技术架构1. 技术栈组成2. 系统架构javascript设计3.效果图

Python如何在Word中生成多种不同类型的图表

《Python如何在Word中生成多种不同类型的图表》Word文档中插入图表不仅能直观呈现数据,还能提升文档的可读性和专业性,本文将介绍如何使用Python在Word文档中创建和自定义各种图表,需要的... 目录在Word中创建柱形图在Word中创建条形图在Word中创建折线图在Word中创建饼图在Word

Python Excel实现自动添加编号

《PythonExcel实现自动添加编号》这篇文章主要为大家详细介绍了如何使用Python在Excel中实现自动添加编号效果,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、背景介绍2、库的安装3、核心代码4、完整代码1、背景介绍简单的说,就是在Excel中有一列h=会有重复

Python FastAPI入门安装使用

《PythonFastAPI入门安装使用》FastAPI是一个现代、快速的PythonWeb框架,用于构建API,它基于Python3.6+的类型提示特性,使得代码更加简洁且易于绶护,这篇文章主要介... 目录第一节:FastAPI入门一、FastAPI框架介绍什么是ASGI服务(WSGI)二、FastAP

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.