【数据结构】顺序查找,折半查找,分块查找的知识点总结及相应的代码实现

目录

1、顺序查找

定义及步骤 

代码实现

2、折半查找

定义及步骤  

代码实现

折半查找判定树 

3、分块查找

定义及步骤 


1、顺序查找

定义及步骤 

        顺序查找的定义:从数据集合的起始位置开始,逐一比较每个数据元素,直到找到所要查找的元素或者遍历完整个数据集合为止。适用于顺序表,链表,表中元素有无顺序都可以。其时间复杂度为O(n),其中n为待查找元素个数。

具体步骤如下:

  1. 从集合的第一个元素开始顺序遍历,直到找到目标元素或者遍历完整个集合。

  2. 若遍历到的元素与目标元素相同,则返回该元素的位置。

  3. 若遍历完整个集合仍未找到目标元素,则返回未找到的标识(通常为-1)。

代码实现

下面是 C 语言实现顺序查找(带哨兵)的示例代码:

#include <stdio.h>#define MAXSIZE 100 // 定义最大容量typedef struct {int data[MAXSIZE+1]; // 数据存储数组,从 data[1] 开始存储数据int len; // 当前长度
} SeqList;// 初始化顺序表
void initList(SeqList *list) {for (int i = 1; i <= MAXSIZE; i++) {list->data[i] = 0;}list->len = 0;
}// 插入元素
int insertList(SeqList *list, int elem) {if (list->len >= MAXSIZE) { // 判断是否已满return 0;}list->data[++list->len] = elem;return 1;
}// 带哨兵的顺序查找
int searchList(SeqList *list, int elem) {int i;list->data[0] = elem; // 设置哨兵for (i = list->len; list->data[i] != elem; i--); // 从后向前遍历查找return i; // 返回查找到的位置
}int main() {SeqList list;initList(&list);insertList(&list, 1);insertList(&list, 3);insertList(&list, 5);insertList(&list, 7);insertList(&list, 9);int pos = searchList(&list, 5);if (pos == 0) {printf("未找到\n");} else {printf("找到了,位置为:%d\n", pos);}return 0;
}

        在上面的代码中,我们定义了一个 SeqList 结构体来实现顺序表,其中包含了数据存储数组和当前长度。使用 initList 函数进行初始化,使用 insertList 函数插入数据。在 searchList 函数中,我们设置了一个哨兵,然后从后向前遍历查找,如果找到则返回位置,否则返回 0 表示未找到。在主函数中,我们创建了一个顺序表,插入了一些数据,然后进行查找,输出查找结果。

 

2、折半查找

定义及步骤  

        折半查找(Binary Search)又称为二分查找,是一种基于比较目标值和数组中间元素的查找算法。该算法的前提条件是数组必须已经有序。只适用于顺序表,仅适用于顺序存储结构,不适用于链式存储结构。

具体实现过程为:

1. 定义左右指针,分别指向数组的第一个元素和最后一个元素。

2. 然后取中间元素的下标,将目标值与此元素进行比较。如果目标值等于数组中间元素的值,则直接返回中间元素的下标。

3. 如果目标值小于数组中间元素的值,则将右指针移动到中间元素的左边一位。

4. 如果目标值大于数组中间元素的值,则将左指针移动到中间元素的右边一位。

5. 重复步骤2~4,直到目标值与中间元素相等或者左右指针相遇。

6. 如果左右指针相遇时,仍没有找到目标值,则表示该数组中没有目标值。

折半查找算法的时间复杂度是O(logN),相对于顺序查找的时间复杂度O(N)而言,折半查找具有更高的效率。

代码实现

下面是 C 语言实现折半查找的示例代码:

#include <stdio.h>int binarySearch(int array[], int left, int right, int x) {while (left <= right) {int mid = left + (right - left) / 2;if (array[mid] == x) {return mid;}else if (array[mid] < x) {left = mid + 1;}else {right = mid - 1;}}return -1; //表示未找到
}int main() {int array[] = {1, 3, 5, 7, 9, 11};int x = 5;int n = sizeof(array) / sizeof(array[0]);int result = binarySearch(array, 0, n - 1, x);if (result == -1) {printf("未找到该元素\n");}else {printf("元素在数组中的索引是:%d\n", result);}return 0;
}

        上述代码中,binarySearch函数的参数依次是数组array、数组左边界left、数组右边界right和要查找的元素x。函数通过while循环不断缩小查找范围,最终返回要查找元素在数组中的索引。在主函数中,我们定义了一个有序数组,然后调用binarySearch函数查找元素5在数组中的位置。如果返回-1,则表示未找到该元素;否则,返回元素在数组中的索引。

        注意:该算法要求在查找之前需要先对数组进行排序。因此,如果数组没有排序,需要先调用排序算法进行排序,再进行查找。

折半查找判定树 

        折半查找判定树(Binary Search Decision Tree,BSDT)是一种二叉树,用于解决折半查找(Binary Search)问题。在BSDT中,每个节点代表一个比较操作,左节点表示小于比较值,右节点表示大于比较值。叶节点代表查找成功的结果,非叶节点代表查找失败的结果。

例如,对于一个长度为7的有序数组[1, 2, 3, 4, 5, 6, 7],对应的BSDT如下图所示:

                ______4______/            \___2___          __6__/       \        /     \1         3      5       7

        在BSDT中,从根节点(4)开始,如果要查找数字3,则先和根节点比较,由于3小于4,因此向左子节点(2)移动。然后再和2节点比较,由于3大于2,因此向右子节点(3)移动。最终到达叶节点,查找成功。

        对于长度为n的有序数组,BSDT的高度为log₂(n),因为每次比较可以剔除一半的数据,因此最多需要比较log₂(n)次。由于BSDT的高度与数据的顺序无关,因此对于任何有序数组,BSDT都可以处理。

        虽然BSDT的时间复杂度是O(log₂(n)),与折半查找一样,但是BSDT比折半查找更适合用于动态数据集合,因为BSDT可以实时更新,支持插入、删除等操作。

3、分块查找

定义及步骤 

        分块查找是一种查找算法,它是一种特殊的二分查找,用于在一组有序的数据中查找特定元素。分块查找主要用于在数据量大时,可以减少比较次数,快速查找所需的元素。

分块查找的过程分为以下几个步骤:

  1. 将数据分成若干个块:将查找的数据分割为若干块,块的大小可自行决定。每一块内的元素是有序的,块与块之间的元素大小可以不同。

  2. 对每一块内的元素建立索引:对每一块内的元素建立索引,索引可以是一个指向元素位置的指针或是一个存储最大元素值的数组。

  3. 使用二分查找在索引中查找所在块:根据查找的元素值,在索引中使用二分查找找到相应的块。

  4. 在所在块中进行线性查找:在所在块中使用线性查找查找所需元素,直到找到与之相等的元素或者超出所在块的范围为止。

  5. 返回查找结果:如果找到所需的元素,则返回该元素的位置;如果未找到,则返回不存在的信息。

        需要注意的是,分块查找的块大小和索引的大小对算法的效率有很大影响。一般来说,块的大小不要太大,索引的大小不要太小,这样才能充分利用分块查找的优势,减少查找次数,提高查找效率。

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/141746.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

哈希表的模拟实现

unordered_set: 接口函数&#xff1a; 对应的应用&#xff1a; unrodered_map: 对应的函数接口&#xff1a; 对应的应用&#xff1a; 比较set和unordered_set的效率&#xff1a; 可以看到各个方面hashset是优于set的。 哈希表的模拟实现&#xff1a; 哈希表的实现分为两种&…

什么是Peppol ID?如何创建?

Peppol 网络的两大优势是安全和高效&#xff0c;由于Peppol 最常用于电子发票&#xff0c;因此这些优势在电子发票上展露无遗。相比之下&#xff0c;通过电子邮件发送 PDF 格式的发票和其他文件不仅处理成本较高&#xff0c;而且容易出现发票欺诈。 如果您所在的公共部门组织或…

华为云云耀云服务器 L 实例评测:快速建站的新选择,初创企业和开发者的理想之选

华为云云耀云服务器 L 实例评测&#xff1a;快速建站的新选择&#xff0c;初创企业和开发者的理想之选 文章目录 华为云云耀云服务器 L 实例评测&#xff1a;快速建站的新选择&#xff0c;初创企业和开发者的理想之选导语&#xff1a;摘要&#xff1a; 正文产品概述部署简易性步…

使用免费软件将数据从机械硬盘克隆到固态硬盘!

正如大家所知道的那样&#xff0c;固态硬盘无论是在读写速度、功耗、噪声还是在耐用性等许多方面都比机械硬盘要更好&#xff0c;所以现在有越来越多的人想要使用升级硬盘&#xff0c;将自己的旧机械硬盘克隆到固态硬盘&#xff0c;从而优化计算机的性能。 目前市面上…

1、Elasticsearch 8.X 概述与安装

第1章 Elasticsearch 8.X 概述 1.1 Elasticsearch 8.X 距 2019 年 Elasticsearch 上一大版本 7.0 发布至今已经过去了 3 年。2022 年 2 月 11 日&#xff0c;Elasticsearch 发布了全新的 8.0 正式版本&#xff0c;这着实给了我们不 小的惊喜&#xff01;新版本中通过改进 Elas…

局域网点歌系统

网盘下载 1、先打开服务端&#xff0c;设置好IP地址 2、客户端打开连接服务器 3、客户端点歌&#xff0c;服务器即可播放

【RV1103】RTL8723bs (SD卡形状模块)驱动开发

文章目录 前言硬件分析Luckfox Pico的SD卡接口硬件原理图LicheePi zero WiFiBT模块总结 正文Kernel WiFi驱动支持Kernel 设备树支持修改一&#xff1a;修改二&#xff1a; SDK全局配置支持 wifi全局编译脚本支持编译逻辑拷贝rtl8723bs的固件到文件系统的固定目录里面去 上电后手…

jvs-rules(规则引擎)和jvs智能bi(自助式数据分析)9.22更新内容

规则引擎更新功能 新增: 1.新增节点匹配筛选 用于做多个条件的数据筛选&#xff0c;以便将符合条件的数据传递给下一个节点进行处理&#xff0c;通常用于实现复杂的查询逻辑。 2.复合变量节点新增判断条件选项说明 用户可以根据自己的需求&#xff0c;为复合变量节点添加不…

深入学习计算机组成原理文章体系

大家好&#xff0c;欢迎阅读《计算机组成原理》的系列文章&#xff0c;本系列文章主要教内容是从零学习计算机组成原理&#xff0c;内容通俗易懂&#xff0c;大家好好学习吧&#xff01;&#xff01;&#xff01; 更多的优质内容&#xff0c;请点击以下链接查看哦~~ 序号链接…

Java深入理解线程的三大特性

目录 1 CPU缓存导致可见性问题2 线程切换导致原子性问题3 性能优化导致有序性问题4 JMM(Java Memory Model)5 volatile6 synchronized 1 CPU缓存导致可见性问题 线程的三大特性&#xff1a; 可见性&#xff1a;Visibility有序性&#xff1a;Ordering原子性&#xff1a;Atomic…

ShapeableImageView 不只是圆形ImageView

偶然间看到了这位老哥的 https://juejin.cn/post/6869376452040196109#comment 文章&#xff0c;发现了ShapeableImageView–一个多形状的ImageView &#xff0c;虽然似乎发布了很久了&#xff0c;现在学习不晚。 效果图 布局文件 <com.google.android.material.imageview.S…

图形处理软件Photoshop Elements 2020 mac中文版 ps简化版

Photoshop Elements 2020 mac是一款非常实用的图形处理工具。ps elements 2020 mac中文版可以帮助您自动生成照片和视频作品的功能&#xff0c;采用Adobe Sensei AI技术可进行图像组织、编辑和创建等。Photoshop Elements 2020 for Mac激活版可以帮助您轻松整理照片和视频&…

【LeetCode热题100】--189.轮转数组

189.轮转数组 数组翻转&#xff1a; 当我们将数组的元素向右移动k次后&#xff0c;尾部k mod n个元素会移动至数组 头部&#xff0c;其余元素向后移动k mod n个位置 该方法为数组的翻转&#xff1a;我们可以先将所有元素翻转&#xff0c;这样尾部k mod n个元素就被移至数组头…

ROS2 从头开始:第 08/8回 - 使用 ROS2 生命周期节点简化机器人软件组件管理

一、说明 欢迎来到我在 ROS2 上的系列的第八部分。对于那些可能不熟悉该系列的人,我已经涵盖了一系列主题,包括 ROS2 简介、如何创建发布者和订阅者、自定义消息和服务创建、

医学影像SAM

医学影像SAM 1. 医学影像SAM1.1. MedSAM1.2. SAM-Adapter1.3. Medical-SAM-Adapter1.4. sam-med2d1.5. MS-SAM 下面整理了一些比较好的博客。 1. 医学影像SAM 由于sam在医学影像上表现不是特别好&#xff0c;在该类型数据集上就需要再训练。 1.1. MedSAM MedSAM&#xff1a…

WebGL绘制圆形的点

目录 前言 如何实现圆形的点&#xff1f; 片元着色器内置变量&#xff08;gl_FragCoord、gl_PointCoord&#xff09; gl_PointCoord的含义 示例程序&#xff08;RoundedPoint.js&#xff09; 代码详解 前言 本文将讨论示例程序RoundedPoint&#xff0c;该程序绘制了圆…

Tomcat 开启远程调试

Tomcat 部署的 war包工程开启远程调试 Linux服务器下&#xff0c;编辑Tomcat bin 目录下的 startup.sh 文件 vim startup.sh在第一行加入&#xff1a;(不换行&#xff0c;在同一行) declare -x CATALINA_OPTS"-server -Xdebug -Xnoagent -Djava.compilerNONE -Xrunjdwp:…

vue3+eleement plus日历选择季度

<template><div class"el-quarter-wrap"><el-popover width"280" v-model"visible"><template #reference><el-input v-model"quarterDate" placeholder"请选择季度" clearable :prefix-icon&qu…

[old]TeamDev DotNetBrowser Crack

TeamDev DotNetBrowser将 Chromium Web 浏览器添加到您的 .NET 应用程序中。在 WPF 和 WinForms 中显示现代网页。使用 DOM、JS、网络、打印等。在 Windows x86/x64/ARM64、macOS x64/Apple Silicon、Linux x64/ARM64 上运行&#xff0c;支持.NET Framework 4.5 特征 HTML5、C…

手机资讯:华为Mate60 Pro上手体验三天的使用体验

最近华为Mate60 Pro开售的消息引爆了整个数码科技圈&#xff0c;毕竟还没开发布会就直接开售新机&#xff0c;这放在整个手机界都是绝无仅有的&#xff0c;并且华为也官方放出了华为Mate60系列的所有参数配置&#xff0c;但唯独没有公开芯片型号和网络信号类型&#xff0c;不免…