当前位置: 首页 > news >正文

查找算法复习

先序

在了解查找算法之前,需要熟悉几个概念,不然后面容易产生理解错误。

查找表:即被查找的对象,通常由几个关键字组成。

关键字:就是数据项、字段的意思。关键字有主次之分,其中主关键字取值是唯一的。

查找长度:给定的关键字在查找表中的比较次数。(查找就是拿要找的数在对应的字段中一个个比较)

静态、动态查找:静态查找只执行查找操作(判断有无和位置在哪),不改变数据;动态查找除了查找还会改变数据。

一、顺序查找(静态查找)

原理:极其简单,就是拿给定值和对应的关键字中的所有数按照指定顺序(从前到后等)一个个比较知道找到或比较完所有值。

考点:顺序查找包括不带监视哨和带监视哨两种类型

不带监视哨的顺序查找

def SeqSearch(self, key):iPos = 0    # 数据元素在查找表中的位置,从第一个开始while iPos < self.length and self.data[iPos] != key:    iPos += 1    # 只要没找到就往后加1return (iPos if iPos < self.length else -1)    # 找到了返回对应位置;没找到返回-1

上述代码中我们需要判断iPos < self.length,即防止越界。为了提高效率,可以把查找表的第一个元素作为监视哨。

带监视哨的顺序查找

def SeqSearch(self, key):self.data[0].key = key    # 将第一个元素作为监视哨iPos = self.length - 1    # 从最后一个数据开始比较while self.data[iPos].key != key:iPos -= 1    # 没找到往前加而不是减一,就不可能越界,也就不用判断。return iPos if iPos > 0 else -1

二、折半查找(静态查找)

条件:折半查找要求查找表必须是有序的

过程:

  1. 首先确定查找范围(左边low, 右边high,两者差大于等于0就有范围),若范围为空则查找失败

  1. 若范围不为空,则在查找范围的中间位置比较,若相同则查找成功

  1. 若小于中间数,则在中间数左边部分(low不变,high为中间位置减一)继续按照上述步骤查找(确定查找范围,比较中间数)

  1. 若大于中间数,则在中间数右边部分(high不变,low为中间位置加一)继续按照上述步骤查找(确定查找范围,比较中间数)

三、二叉排序树(动态查找)

  • 二叉排序树的概念:

它要么是空树,要么是满足以下性质的二叉树:

① 若根结点的左子树非空,则左子树中所有结点的值都小于根结点的值。

② 若根结点的右子树非空,则右子树中所有结点的值都大于根结点的值。

③ 根结点的左、右子树均是一棵二叉排序树。

  • 二叉排序树的创建:采用插入算法。很简单,根据给定的顺序,第一个被插入的作为根节点,后面插入的与根节点比较按照其性质放置在左右子树中。

例:关键字{11,12,8,5,10,15}

关键字{5,12,8,11,10,15}

  • 二叉排序树的查找:类似于折半查找,从根节点开始比较,然后往左右子树的根节点比较,就类似与折半查找比较中间位置。

  • 二叉树删除关键字:

分三种情况,被删除的节点为叶子结点、只有左子树或者右子树、左右子树都有。

前两种很简单,第一种直接删了,其双亲的指针域改成空;第二种让双亲指针指向下一个根节点即可

第三种提一下,有两种办法,下图的是其中一种,即找到要被删除的节点的左子树中最大的节点。然后把该删除的节点删掉用左子树的最大的节点补充即可。

当然还有第二种办法,就是找到右子树中最小的节点然后把该删除的删除,用右子树最小的节点代替即可。

四、平衡二叉树、B-树的概念(动态查找)

平衡二叉树:二叉树查找中二叉树的高度越小平均查找长度就会越小,所以平衡二叉树就是使得二叉树的深度尽可能的小并满足原来二叉树性质的特殊的二叉树。别名AVL树

平衡二叉树的性质:每个节点的左右子树的深度之差的绝对值小于等于1(-1,0,1)

B-树:解决数据元素太大查找效率低下的问题。

相关文章:

查找算法复习

先序在了解查找算法之前&#xff0c;需要熟悉几个概念&#xff0c;不然后面容易产生理解错误。查找表&#xff1a;即被查找的对象&#xff0c;通常由几个关键字组成。关键字&#xff1a;就是数据项、字段的意思。关键字有主次之分&#xff0c;其中主关键字取值是唯一的。查找长…...

腾讯前端必会面试题(必备)

如何提取高度嵌套的对象里的指定属性&#xff1f; 有时会遇到一些嵌套程度非常深的对象&#xff1a; const school {classes: {stu: {name: Bob,age: 24,}} }像此处的 name 这个变量&#xff0c;嵌套了四层&#xff0c;此时如果仍然尝试老方法来提取它&#xff1a; const {…...

探访上汽通用武汉奥特能超级工厂

上汽通用汽车在电动化和智能网联化新技术领域投入了700亿大洋&#xff0c;武汉奥特能超级工厂就是其中一个重点项目。这个工厂已经投产&#xff0c;将成为上汽通用汽车的新能源生产基地&#xff0c;加速奥特能平台车型的推出。 最近别克推出了Electra E5&#xff0c;它是别克第…...

【Linux】线程函数和线程同步详细整理(金针菇般细)

目录 一&#xff0c;线程函数 1.获取当前线程ID 2.创建线程 3.退出线程 4.阻塞线程 5.分离线程 6.取消线程 7.线程比较 8.测试代码&#xff08;线程函数总结&#xff09; 二&#xff0c;线程同步 1.互斥锁 2.读写锁 3.条件变量 4.信号量 一&#xff0c;线程函数 …...

Python学习笔记6:抽象

抽象 函数 判断某个对象是否可调用&#xff0c;可使用内置函数callable >>> import math >>> x 1 >>> y math.sqrt >>> callable(x) False >>> callable(y) True斐波那契数组 def fibs(num): result [0, 1] for i i…...

自己手写一个redux

提起 Redux 我们想到最多的应该就是 React-redux 这个库&#xff0c;可是实际上 Redux 和 React-redux 并不是同一个东西, Redux 是一种架构模式&#xff0c;源于 Flux。 React-redux 是 Redux 思想与 React 结合的一种具体实现。 在我们使用 React 的时候&#xff0c;常常会遇…...

mysql调优参数

my.conf [client] port 端口 socket sokcet位置 [mysqld] basedir mysql位置 port 3306 socket sokcet位置 datadir data目录 pid_file mysqld.pid位置 bind_address 0.0.0.0 lower_case…...

JavaEE简单示例——再插入的同时获取插入的主键列

简单介绍&#xff1a; 在某些时候&#xff0c;我们在插入完成一条语句之后&#xff0c;我们会想要返回之前插入的这条语句的主键列的数据&#xff0c;进行下一步的展示或者修改&#xff0c;我们就可以使用MyBatis的主键回写功能&#xff0c;帮助我们获取插入成功的一条数据的主…...

sql语句练习

一、现有以下两张表&#xff1a;第一张表名为cust&#xff0c;其表结构如下&#xff1a;第二张表名为mark&#xff0c;其表结构如下:1) [5分]请写出计算 所有学生的英语平均成绩的sq|语句。2) [5分]现有五 个学生,其学号假定分别为11,22,33,44,55;请用一条SQL语句实现列出这五个…...

广州蓝景—结合chatGPT下的教育模式变化

最近爆火的人工智能AI聊天工具ChatGPT&#xff0c;不仅在互联网&#xff0c;更是在各行各业中&#xff0c;得到了广泛的传播&#xff0c;应该没有哪一个不知道它的存在&#xff0c;但其实你又是否知道&#xff0c;其实ChatGPT是一类模型的统称&#xff0c;随着人工智能的快速发…...

大数据框架之Hadoop:MapReduce(三)MapReduce框架原理——shuffle机制

3.3.1Shuffle机制 Map方法之后&#xff0c;Reduce方法之前的数据处理过程称之为Shuffle。 3.3.2Partition分区 1、问题引出 要求将统计结果按照条件输出到不同文件中&#xff08;分区&#xff09;。比如&#xff1a;将统计结果按照手机归属地不同省份输出到不同文件中&#…...

4|无线传感器网络与应用|无线传感器网络原理及方法-许毅版|第3章:无线传感器网络通信-3.1协议结构 3.2物理层|青岛科技大学|课堂笔记

第3章&#xff1a;无线传感器网络通信3.1协议结构3.1.1 OSI参考模型1.网络通信协议MAC层和物理层采用IEEE 802.15.4协议*(1)物理层wsn物理层负责信号的调制和数据的收发&#xff0c;传输介质&#xff1a;无线电、红外线、光波等。(2)数据链路层wsn数据链路层负责数据成帧、帧检…...

关机时,如何控制systemd服务的关闭顺序

关机时&#xff0c;如何控制systemd服务的关闭顺序? 在工作中&#xff0c;我们通常遇到的问题是&#xff0c;如何控制systemd服务的启动顺序&#xff0c;同志们第一反应就会是使用Before或者After去进行控制。 问题来了&#xff0c;如果服务启动时没有顺序要求&#xff0c;但…...

关于MySQL镜像构建过程中添加自动初始化数据库

需求描述一般而言&#xff0c;我们在拉取了 mysql 镜像并运行之后&#xff0c;其中的并不会存在我们自定义的数据库&#xff0c;都是在镜像运行后&#xff0c;自己主动导入数据库&#xff0c;那么有没有方式可以一运行 mysql 镜像&#xff0c;对应生成的 mysql 容器中就有我们自…...

CS144-Lab2

实验架构 除了写入传入流之外&#xff0c;TCPReceiver 还负责通知 sender 两件事&#xff1a; “First unassembled” 字节的索引&#xff0c;称为“acknowledgment”或 “ackno”。这是接收方需要来自发送方的第一个字节。“first unassembled ” 索引和“first unacceptable…...

Linux内核驱动之efi-rtc

Linux内核驱动之efi-rtc1. UEFI与BIOS概述1.1. BIOS 概述1.1.1. BIOS缺点&#xff1a;1.1.2. BIOS的启动流程1.2 UEFI 概述1.2.1 Boot Sevices&#xff1a;1.2.2. Runtime Service&#xff1a;1.2.3. UEFI优点&#xff1a;1.2.4. UEFI启动过程&#xff1a;1.3 Legacy和UEFI1.4 …...

Java 字符串

文章目录一、API二、String1. String 构造方法2. String 对象的特点3. 字符串的比较4. 用户登录案例5. 遍历字符串6. 统计字符次数7. 拼接字符串8. 字符串反转三、StringBuilder1. 构造方法2. 添加及反转方法3. 与 String 相互转换4. 拼接字符串升级版5. 字符串反转升级版一、A…...

麦克风阵列波束基本概念理解

波束形成 本质上是设计合适的滤波器&#xff0c;对于一类固定滤波器系数的阵列来说&#xff0c;无论输入信号或者噪声信号的统计特征如何&#xff0c;其滤波器系数固定不变&#xff0c;此类波束形成叫Fixed Beamforming&#xff0c;固定波束形成好比传统数字信号处理里面的经典…...

JAVA保姆式JDBC数据库免费教程之02-连接池技术

连接池 连接池概念 ​ 概念&#xff1a;其实就是一个容器(集合)&#xff0c;存放数据库连接的容器。 当系统初始化好后&#xff0c;容器被创建&#xff0c;容器中会申请一些连接对象&#xff0c;当用户来访问数据库时&#xff0c;从容器中获取连接对象&#xff0c;用户访问完…...

视频片段怎么做成gif图?快试试这2种方法

动态gif图片作为当下非常常用的表情包&#xff0c;其丰富的内容生动的画面深受大众喜爱。那么&#xff0c;当我们想要将电影或是电视剧中的某一片段做成gif动态图片的时候&#xff0c;要如何操作呢&#xff1f;接下来&#xff0c;给大家分享两招视频转化gif的小窍门–使用【GIF…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...