数据结构-查找（四）总结与对比
查找算法总结
文章目录
- 查找算法总结
- 一、查找的基本概念
- 二、顺序查找法
- 适用场景
- 三、分块查找法
- 适用场景
- 四、折半查找法（Binary Search）
- 适用场景
- 五、树型查找
- 1. 二叉搜索树（BST）
- 2. 平衡二叉树（AVL）
- 3. 红黑树（Red-Black Tree）
- 对比表格
- 六、B树及其基本操作、B+树的基本概念
- 1. B树
- 2. B+树
- 七、散列（Hash）表
- 八、字符串模式匹配
- 总结与对比
查找算法是计算机科学中的基本算法之一，用于在数据集合中查找特定元素。常见的查找算法有顺序查找、分块查找、折半查找、树型查找（如二叉树、平衡二叉树、红黑树）、B树及B+树、散列表以及字符串模式匹配算法。本文将对这些查找方法进行总结和对比，帮助大家更好地理解和掌握这些查找技术。
一、查找的基本概念
查找（Search）是指在一定的数据集合中寻找目标元素的位置或判断元素是否存在的过程。常见的数据结构包括数组、链表、树、图等，不同的数据结构和查找算法对查找效率有着显著影响。
二、顺序查找法
顺序查找是最基本的查找方法，按顺序逐个遍历数据集合，直到找到目标元素为止。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 优点：简单直观，无需排序。
- 缺点：效率较低，尤其是在数据量大的时候。
适用场景
适用于小规模或未排序的线性数据结构，如链表或无序数组。
三、分块查找法
分块查找将数据集合分为若干个块，在每个块内进行顺序查找，并通过块的索引来减少查找范围。
- 时间复杂度：O(√n)
- 空间复杂度：O(√n)
- 优点：比顺序查找更高效。
- 缺点：需要额外的空间存储块信息，且块内查找仍然是顺序查找。
适用场景
适用于数据量较大、未排序的情况，且可以接受额外的空间开销。
四、折半查找法（Binary Search）
折半查找要求数据集合必须是有序的，通过不断将查找范围减半，直到找到目标元素。
- 时间复杂度：O(log n)
- 空间复杂度：O(1)（递归时为O(log n)）
- 优点：比顺序查找效率高，尤其适用于大规模数据。
- 缺点：只能用于已排序的数据，且排序本身需要额外的时间。
适用场景
适用于已排序的数组或链表。
五、树型查找
1. 二叉搜索树（BST）
二叉搜索树是一种树形结构，其中每个节点的值大于其左子树的所有节点值，小于其右子树的所有节点值。
- 时间复杂度：平均O(log n)，最坏情况O(n)
- 空间复杂度：O(n)
- 优点：可以进行高效的动态插入和删除。
- 缺点：在不平衡的情况下，性能会退化为顺序查找。
2. 平衡二叉树（AVL）
平衡二叉树是一种特殊的二叉搜索树，通过旋转操作来保持树的平衡性，从而保证最坏情况下的时间复杂度。
- 时间复杂度：O(log n)
- 空间复杂度：O(n)
- 优点：查找、插入、删除操作均能保持在O(log n)时间复杂度。
- 缺点：需要额外的时间和空间来维持平衡。
3. 红黑树（Red-Black Tree）
红黑树是一种自平衡的二叉查找树，它通过颜色标记节点，并根据一定的规则进行平衡操作，保证树的平衡性。
- 时间复杂度：O(log n)
- 空间复杂度：O(n)
- 优点：在动态插入和删除时，保持高效。
- 缺点：比AVL树的实现稍复杂，但性能差距不大。
对比表格
| 查找方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 二叉搜索树 | 平均O(log n)，最坏O(n) | O(n) | 动态插入删除 | 不平衡时性能退化 |
| 平衡二叉树（AVL） | O(log n) | O(n) | 高效动态操作 | 需要额外的平衡维护 |
| 红黑树 | O(log n) | O(n) | 动态操作高效 | 实现复杂 |
六、B树及其基本操作、B+树的基本概念
1. B树
B树是一种自平衡的树数据结构，适用于大规模的数据存储和检索，常用于数据库和文件系统中。
- 时间复杂度：O(log n)
- 空间复杂度：O(n)
- 优点：能有效减少磁盘I/O操作，适合大规模数据存储。
- 缺点：比二叉树结构复杂，且操作较为繁琐。
2. B+树
B+树是B树的一种变种，所有数据都存储在叶子节点，非叶子节点仅用于索引。
- 时间复杂度：O(log n)
- 空间复杂度：O(n)
- 优点：适合范围查询，性能稳定。
- 缺点：内存开销较大。
七、散列（Hash）表
散列查找通过一个散列函数将元素映射到一个固定大小的数组中，查找时可以直接通过索引访问。
- 时间复杂度：O(1)（平均情况），最坏O(n)（哈希冲突严重时）
- 空间复杂度：O(n)
- 优点：查找、插入、删除操作都能保持常数时间复杂度。
- 缺点：哈希冲突会影响性能，且需要合适的散列函数。
八、字符串模式匹配
字符串模式匹配用于在一个大字符串中查找是否包含某个子字符串。常见的算法有KMP算法、Rabin-Karp算法、Boyer-Moore算法等。
- 时间复杂度：O(n)（KMP）
- 空间复杂度：O(m)（KMP）
- 优点：适用于大量字符串匹配。
- 缺点：有些算法实现复杂，需要额外的空间。
总结与对比
以下是常见查找算法的对比，帮助大家更直观地理解不同算法的特点和适用场景。
| 查找方法 | 时间复杂度 | 空间复杂度 | 优缺点 |
|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 简单，适用于小数据集，效率低 |
| 分块查找 | O(√n) | O(√n) | 比顺序查找更高效，适用于大数据集 |
| 折半查找 | O(log n) | O(1) | 只适用于有序数据，效率高 |
| 二叉搜索树 | 平均O(log n)，最坏O(n) | O(n) | 动态插入删除，性能不稳定 |
| 平衡二叉树（AVL） | O(log n) | O(n) | 高效动态操作，需额外平衡维护 |
| 红黑树 | O(log n) | O(n) | 动态操作高效，稍复杂 |
| B树 | O(log n) | O(n) | 适用于大规模数据存储 |
| B+树 | O(log n) | O(n) | 范围查询高效，内存开销大 |
| 哈希表 | O(1) | O(n) | 查找快速，但哈希冲突影响性能 |
| 字符串匹配 | O(n) | O(m) | 适用于字符串搜索，效率高 |
相关文章：
数据结构-查找（四）总结与对比
查找算法总结 文章目录 查找算法总结一、查找的基本概念二、顺序查找法适用场景 三、分块查找法适用场景 四、折半查找法（Binary Search）适用场景 五、树型查找1. 二叉搜索树（BST）2. 平衡二叉树（AVL）3. 红黑…...
c++总复习
一、什么是 C 中的函数对象？它有什么特点？ 在 C 中，函数对象（Function Object）也称为仿函数（Functor），它是一个类的实例，该类重载了函数调用运算符()，使得这个…...
AJAX一、axios使用，url组成（协议，域名，资源路径）查询参数和化简，错误处理，请求/响应报文，状态码，接口文档，
一、AJAX是什么 概念 ： AJAX是一种与服务器（后端）通信的技术 二、请求库axios的基本用法 1导包 2使用 // 1. 发请求 axios({ url: 请求地址 }).then(res > { // 2.接收并使用数据 }) <body><p class"province"…...
Python学习笔记
MJ大神的Python课，课堂笔记 int 和float运算结果是 float除法（/）的结果是float整除（//），向下取整(floor)int 和 int 进行整除（//）,得到的结果是int 绘制一个填充色边框色 import …...
开源 - Ideal库 - Excel帮助类，TableHelper实现（三）
书接上回，我们今天继续讲解实现对象集合与DataTable的相互转换。 01、把表格转换为对象集合 该方法是将表格的列名称作为类的属性名，将表格的行数据转为类的对象。从而实现表格转换为对象集合。同时我们约定如果类的属性设置了DescriptionAttribute特性…...
ceph手动部署
ceph手动部署 一、 节点规划 主机名IP地址角色ceph01.example.com172.18.0.10/24mon、mgr、osd、mds、rgwceph02.example.com172.18.0.20/24mon、mgr、osd、mds、rgwceph03.example.com172.18.0.30/24mon、mgr、osd、mds、rgw 操作系统版本： Rocky Linux release …...
macOS 开发环境配置与应用开发指南
macOS 开发环境配置与应用开发指南 macOS作为苹果公司推出的操作系统，因其稳定性、优雅的用户界面和强大的开发支持，已成为开发者和创意专业人士的首选平台之一。无论是开发iOS、macOS桌面应用，还是Web应用、跨平台程序，macOS都提…...
自动化是语法，智能化是语义与语用
自动化与智能化可以从语言学的角度来进行类比和探讨。 1. 自动化是语法 自动化可以类比为“语法”的部分，因为它关注的是操作过程的规则、结构和执行方式。语法是语言中关于词汇、句子结构和规则的系统，它提供了语言运作的框架和规范。类似地，…...
基于DHCP，ACL的通信
该问题为华为的学习资料 1.首先把所有的PC机全部设置为DHCP 2.配置地址 3.ospf 4.dhcp 5.acl AR1 dhcp en interface GigabitEthernet0/0/0ip address 192.168.1.254 255.255.255.0 dhcp select global interface GigabitEthernet0/0/1ip address 10.1.12.1 255.255.255.…...
Unity跨平台基本原理
Unity跨平台基本原理 Unity跨平台基本原理微软的.Net是什么微软做 .Net平台的目的如何实现的.Net跨语言？总结 .Net Framework.Net Framework的体系结构CLR总结 如何实现的跨平台？.Net Core.Net FrameWork 到 .Net CoreMonoMono如何实现跨平台总结如何实现…...
基于 Python、OpenCV 和 PyQt5 的人脸识别上课打卡系统
大家好，我是Java徐师兄，今天为大家带来的是基于 Python、OpenCV 和 PyQt5 的人脸识别上课签到系统。该系统采用 Python 语言开发，开发过程中采用了OpenCV框架，Sqlite db 作为数据库，系统功能完善 ，实用性强…...
IDEA的简易安装思路
IDEA(本身就是Java开发的)：是目前为止开发Java效率最高的工具，但正版收费……（eclipse的话不好说，反正还是随主流吧） 使用IDEA的前提：必须先安装JDK【否则直接使用IDEA工具来运行程序是无效的，它…...
【实战】在Koa.js中实现文件上传的接口 （本地存储）
目录 环境准备 使用 koa-body 中间件获取上传的文件 使用 Postman 测试 使用 koa-static 中间件生成图片链接 编写前端页面上传文件 文件上传是一个基本的功能，每个系统几乎都会有，比如上传图片、上传Excel等。那么在Node Koa应用中如何实现一个支持…...
flink学习（10）——allowedLateness/测道输出
allowedLateness(lateness: Time) 水印：短期延迟，达到条件后触发计算并且关闭窗口（触发关闭同时进行） 水印allowedLateness : 短期延迟 等待长期延迟效果 1、达到水印条件后，会触发窗口计算，但是不关闭窗口…...
微信小程序按字母顺序渲染城市 功能实现详细讲解
在微信小程序功能搭建中，按字母渲染城市会用到多个ES6的方法，如reduce，map，Object.entries()，Object.keys() ，需要组合熟练掌握，才能优雅的处理数据完成渲染。 目录 一、数据分析 二、数据处理 …...
openjdk17 jvm 对象 内存溢出 在C++源码体现
##java大对象类 public class MiBigObject {private String f1;private String f2;private String f3;private String f4;private String f5;private String f6;private String f7;private String f8;private String f9;private String f10;private String f11;private String…...
【软考速通笔记】系统架构设计师⑧——系统质量属性与架构评估
文章目录 一、前言二、软件系统质量属性2.1 开发期质量属性2.2 运行期质量属性 三、质量属性场景描述四、系统架构评估方法4.1 方法分类4.2 软件架构分析方法4.3 架构权衡分析法4.4 成本效益分析法 一、前言 笔记目录大纲请查阅：【软考速通笔记】系统架构设计师——…...
YOLO系列论文综述（从YOLOv1到YOLOv11）【第5篇：YOLOv3——多尺度预测】
YOLOv3 1 摘要2 YOLOv32.1 相对于v2的改进2.2 网络架构2.3 多尺度预测2.4 YOLOv3结果 YOLO系列博文： 【第1篇：概述物体检测算法发展史、YOLO应用领域、评价指标和NMS】【第2篇：YOLO系列论文、代码和主要优缺点汇总】【第3篇：YOLOv…...
HarmonyOS4+NEXT星河版入门与项目实战（25）------UIAbility启动模式（文档编辑案例）
文章目录 1、启动模式2、Specified启动模式实现步骤3、文档编辑案例1、文件创建2代码实现3、Statge 创建4、添加配置1、启动模式 Singleton启动模式： 每个 UIAbility 只存在一个实例，是默认的启动模式，任务列表中只会存在一个相同的 UIAbilityStandard启动模式： 每次启动 U…...
PyTorch张量运算与自动微分
PyTorch张量运算与自动微分 PyTorch由Facebook人工智能研究院于2017年推出，具有强大的GPU加速张量计算功能，并且能够自动进行微分计算，从而可以使用基于梯度的方法对模型参数进行优化，大部分研究人员、公司机构、数据比赛都使用P…...
在 Ubuntu 20.04 上使用 Lux 下载 Bilibili 视频的详细教程
在 Ubuntu 20.04 上使用 Lux 下载 Bilibili 视频的详细教程 在 Ubuntu 20.04 上使用 Lux 下载 Bilibili（哔哩哔哩）视频的完整和详细步骤如下，包括使用预编译二进制文件的安装方法： 1. 安装依赖 确保你的系统已安装 FFmpeg&…...
1.1 数据结构的基本概念
1.1.1 基本概念和术语 一、数据、数据对象、数据元素和数据项的概念和关系 数据：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。 数据是计算机程序加工的原料。 数据对象：是具有相同性质的数据元素的集合&…...
)
【NebulaGraph】深入了解查询语句(二)
【NebulaGraph】深入了解查询语句 1. NebulaGraph 查询语句概述 1. NebulaGraph 查询语句概述 文档：https://docs.nebula-graph.com.cn/3.8.0/3.ngql-guide/7.general-query-statements/1.general-query-statements-overview/ NebulaGraph 的数据以点和边的形式存…...
Oracle—系统包使用
文章目录 系统包dbms_redefinition 系统包 dbms_redefinition 功能介绍：该包体可以实现将Oracle库下的表在线改为分区结构或者重新定义； 说明：在检查表是否可以重定义和开始重定义的过程中，按照表是否存在主键，参数 o…...
org.apache.commons.lang3包下的StringUtils工具类的使用
前言 相信平时在写项目的时候，一定使用到StringUtils.isEmpty()；StringUtils.isBlank();但是你真的了解他们吗？ 也许你两个都不知道，也许你除了isEmpty/isNotEmpty/isNotBlank/isBlank外，并不知道还有isAnyEmpty/isNon…...
详细介绍Node.js的中间件及使用方法
在Node.js的生态中，中间件（Middleware）是一个不可或缺的概念，它为构建灵活而高效的应用程序提供了强大的支持。以下是对Node.js中间件的详细介绍： 中间件的概念与定义 中间件是一种软件架构的设计模式，用…...
VPC9527同步整流控制器，相对最大电压检测与强力自供电，与MP6908完全PIN TO PIN
VPC9527 是一款高性能的同步整流控制器，它兼容 CCM 和 DCM 两种模式，最大工作频率高达 700kHz；可 通过 SEL 引脚的逻辑电压来选择 400nS 或 800nS 两个关断检测的屏蔽时间；可通过 VLC 引脚来调整限压导通的 参数，以便与所选同步整流管的参数相匹配，获得适应的最优性能；它…...
【聚类】主成分分析 和 t-SNE 降维
1 主成分分析PCA PCA 是一种线性降维技术，旨在通过选择具有最大方差的特征方向（称为主成分）来压缩数据，同时尽可能减少信息损失。 1.1 原理 1.2 优缺点 from sklearn.decomposition import PCA import matplotlib.pyplot as plt…...
MyBatis框架-日志配置
MyBatis框架的日志配置 MyBatis作为一个封装好的ORM框架，其运行过程我们没有办法跟踪，为了让开发者MyBatis执行流程及执行步骤所完成的工作，MyBatis框架本身支持log4j日志框架，对运行的过程进行跟踪记录。我们只需对MyBatis进行相…...
【数据结构】哈希 ---万字详解
unordered系列关联式容器 在C98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log_2 N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好 的查询是，…...
Python Web 框架
Python 有多个强大的 Web 框架，每个框架都具有不同的特点和应用场景。根据开发者的需求（如开发速度、灵活性、功能等），可以选择适合的框架。以下是一些常见的 Python Web 框架： 1. Django 简介：Django 是一…...
大模型翻译能力评测
1. 背景介绍 随着自然语言处理技术的飞速发展，机器翻译已经成为一个重要的研究领域。近年来，基于大模型的语言模型在机器翻译任务上取得了显著的进展。这些大模型通常具有数亿甚至数千亿的参数，能够更好地理解和生成自然语言。 但是…...
深度学习中的前向传播与损失函数
目录 编辑 前向传播：神经网络的推理过程 什么是前向传播？ 前向传播的步骤 数学表达 代码示例：前向传播 损失函数：衡量预测与真实值的差异 损失函数的定义 损失函数的作用 常见的损失函数 代码示例：损失函…...
MySQL 复合查询
实际开发中往往数据来自不同的表，所以需要多表查询。本节我们用一个简单的公司管理系统，有三张表EMP,DEPT,SALGRADE 来演示如何进行多表查询。表结构的代码以及插入的数据如下： DROP database IF EXISTS scott; CREATE database IF NOT EXIST…...
core API简单示例，并解决403权限验证问题，即何进行进行权限授权以及验证)
Java程序调kubernetes(k8s1.30.7)core API简单示例，并解决403权限验证问题，即何进行进行权限授权以及验证
简单记录问题 一、问题描述 希望通过Java程序使用Kubernetes提供的工具包实现对Kubernetes集群core API的调用，但是在高版本上遇见权限验证问题4xx。 <dependency><groupId>io.kubernetes</groupId><artifactId>client-java</artifact…...
Java安全—原生反序列化重写方法链条分析触发类
前言 在Java安全中反序列化是一个非常重要点，有原生态的反序列化，还有一些特定漏洞情况下的。今天主要讲一下原生态的反序列化，这部分内容对于没Java基础的来说可能有点难，包括我。 序列化与反序列化 序列化：将内存…...
火鸟地方门户系统V8.5系统源码+搭建环境教程
一.介绍 火鸟地方门户系统V8.5源码 系统包含4端： PCH5小程序APP 二.搭建环境 系统环境：CentOS、 运行环境：宝塔 Linux 网站环境：Nginx 1.2.22 MySQL 5.6 PHP-7.4 常见插件：fileinfo ； redis 三.测…...
深度学习：梯度下降法
损失函数 L：衡量单一训练样例的效果。 成本函数 J：用于衡量 w 和 b 的效果。 如何使用梯度下降法来训练或学习训练集上的参数w和b ？ 成本函数J是参数w和b的函数，它被定义为平均值； 损失函数L可以衡量你的算法效果&a…...
Git常用命令
Git是一个优秀的代码版本管理工具，其常用命令包括但不限于以下这些： 一、初始化与配置 git init：在当前目录初始化一个新的Git仓库。git clone [url]：克隆远程仓库到本地。git config：配置Git的各种选项和变量&#…...
css预处理器scss/sass
一、css预处理器sass的诞生 众所周知css并不能算是一们真正意义上的“编程”语言，它本身无法未完成像其它编程语言一样的嵌套、继承、设置变量等工作，仅仅只能用来编写网站样式，如此一来代码就会百年的臃肿难以维护。为了解决css的不足&#…...
磁盘/系统空间占满导致黑屏死机无法开机的解决办法
文章目录 起因具体操作1.重启虚拟机，一直按CtrlShitf进入GRUP界面2.选“Ubuntu高级选项”并回车选择第二个，recovery mode3.4.命令查看磁盘情况5.查找和删除文…...
API 与 SDK 之间的区别
API 与 SDK 之间的区别 很多人在软件开发中经常会分不清 SDK 与 API ，今天就来浅谈一下两者之间的区别。 直白地说，SDK 包含了 API ，是一套完整的，能完成更多功能的工具包，无论你想获取什么样的信息，SDK …...
Lua的环境与热更
一、global_State,lua_State与G表 Lua支持多线程环境，使用 lua_State 结构来表示一个独立的 Lua 线程（或协程）。每个线程都需要一个独立的全局环境。而lua_State 中的l_G指针，指向一个global_State结构，这个就是我们常…...
java八股-分布式服务的接口幂等性如何设计？
文章目录 接口幂等token Redis分布式锁 原文视频链接：讲解的流程特别清晰，易懂，收获巨大 【新版Java面试专题视频教程，java八股文面试全套真题深度详解（含大厂高频面试真题）】 https://www.bilibili.com/…...
鸿蒙学习使用模拟器运行应用（开发篇）
文章目录 1、系统类型和运行环境要求2、创建模拟器3、启动和关闭模拟器4、安装应用程序包和上传文件QA:在Windows电脑上启动模拟器，提示未开启Hyper-V 1、系统类型和运行环境要求 Windows 10 企业版、专业版或教育版及以上，且操作系统版本不低于10.0.18…...
基于 FFmpeg/Scrcpy 框架构建的一款高性能的安卓设备投屏管理工具-供大家学习研究参考
支持的投屏方式有：USB，WIFIADB，OTG，投屏之前需要开启开发者选项里面的USB调试。 主要功能有： 1.支持单个或多个设备投屏。 2.支持键鼠操控。 3.支持文字输入。 4.支持共享剪切板（可复制粘贴电脑端文字到手机端，也可导出手机剪切板到电脑端）。 5.支持视频图片上传，可单…...
ESLint v9.0.0 新纪元：探索 eslint.config.js 的奥秘 （4）
从 v9.0.0 开始，官方推荐的配置文件格式是 eslint.config.js，并且支持 ESM 模块化风格，可以通过 export default 来导出配置内容。 // eslint.config.js export default [{rules: {semi: "error","prefer-const": "…...
电脑还原重置Windows系统不同操作模式
电脑有问题，遇事不决就重启，一切都不是问题！是真的这样吗。其实不然，主机系统重启确实可以自动修复一些文件错误，或者是设置问题，但是，当你由于安装了错误的驱动或者中毒严重，亦或是蓝屏，那么重启这个方子可能就治不了你的电脑了。 那么，除了当主机出现异常故障现象…...
图论2图的应用补充
图论1基础内容-CSDN博客 图的应用 4.1 拓扑排序 拓扑排序针对有向无环图的顶点进行线性排列的算法，使得对于任何来自顶点A指向顶点B的边，A都在序列中出现在B之前。这样的排序存在于有向无环图中，而对于非有向无环图则不存在拓扑排序。 拓扑排…...
非线性模型预测控制（NMPC）算法及其Python实现
目录 非线性模型预测控制（NMPC）算法及其Python实现第一部分：NMPC算法概述1.1 NMPC的定义1.2 NMPC的优点1.3 NMPC的应用领域第二部分：NMPC算法的数学模型2.1 系统建模2.2 目标函数与约束2.3 NMPC算法的求解第三部分：NMPC算法的实现与优化3.1 实现步骤3.2 Python实现3.3 设计…...