数据结构——7.17.2 查找的基本概念、顺序查找和折半查找

2024-04-21 08:04

本文主要是介绍数据结构——7.17.2 查找的基本概念、顺序查找和折半查找,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

7.1&7.2 查找的基本概念、顺序查找和折半查找

1. 基本概念

1.  关键字:数据元素中标识该元素的某个数据项的值,使用基于关键字的查找,查找结果应该是唯一的。2.  查找表的常见操作1.  查找符合条件的数据元素:查得快即可2.  插入、删除某个数据元素:兼顾查找速度和操作便捷3.  查找算法的评价指标1.  查找长度——在查找运算中,需要对比关键字的次数称为查找长度2.  平均查找长度(ASL,Average Search Length)——所有查找过程中进行关键字的比较次数的平均值

2. 顺序查找

也称:线性查找,即遍历,常用于线性表(顺序、链表)

顺序查找,是一种简单的查找方式。这种查找方法从列表的一端开始,顺序搜索直到找到所需的元素为止。

顺序查找的基本思想是:从列表的第一个元素开始,逐个检查每个元素,直到找到所需的元素或搜索到列表的末尾为止。

顺序查找的步骤如下:
  1. 从列表的第一个元素开始,与所要查找的元素进行比较。
  2. 如果相等,则查找成功,返回该元素在列表中的位置。
  3. 如果不相等,则继续向后查找下一个元素。
  4. 重复以上步骤,直到找到所需元素或搜索到列表的末尾。

顺序查找的时间复杂度是O(n),其中n是列表中元素的数量。这是因为在最坏的情况下,可能需要检查列表中的每个元素。虽然顺序查找在某些情况下可能不是最高效的查找方法,但它简单易懂,适用于小型列表或对效率要求不高的场景。

优化思路:将大概率要被查询的值放到前面来;该方法适用于经常需要查询的情况

顺序查找虽然简单易懂,但在处理大型数据集时效率较低。为了优化顺序查找的性能,可以考虑以下几种方法:

  1. 减少比较次数

    • 预处理数据:在搜索前对数据进行排序,可以减少平均情况下的比较次数。虽然排序本身需要时间,但对于多次查找的情况,排序可能是一个值得的预处理步骤。
    • 利用数据的特性:如果数据具有某种模式或分布,可以设计更高效的查找策略。
  2. 使用哨兵或标记

    • 在列表的末尾添加一个哨兵值或标记,这样当查找的元素不存在时,可以更快地停止查找。
  3. 分块查找

    • 将列表分成多个块,每个块内部可以是无序的,但块之间是有序的。首先确定目标元素可能存在的块,然后在该块内进行顺序查找。这种方法结合了顺序查找和索引查找的优点。
  4. 使用更好的数据结构

    • 如果可能的话,使用更高效的数据结构(如哈希表、二分查找树等)来存储和查找数据。这些数据结构提供了更快的查找时间复杂度。
  5. 并行化

    • 在多核处理器或多计算机环境下,可以并行地进行查找操作。将数据分割成多个部分,每个部分由一个处理单元同时搜索。
  6. 缓存优化

    • 对于顺序访问的列表,确保数据在物理内存中是连续的,以减少缓存未命中的次数。
  7. 算法层面的优化

    • 使用更高效的比较算法,比如对于大型整数或浮点数,可以使用更快速的比较方法。

需要注意的是,优化顺序查找的性能通常需要根据具体的应用场景和数据特点来选择合适的方法。在某些情况下,优化可能并不总是值得的,因为可能会增加代码的复杂性和维护成本。因此,在进行优化之前,需要仔细评估需求和性能要求,并确定最合适的优化策略。

3. 折半查找

折半查找,又称“二分查找”,仅适用于有序的顺序表,这是因为顺序表具有随机存储的特性,而链表没有

折半查找,是一种在有序数组中查找某一特定元素的搜索算法。其基本原理是从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或小于中间元素,则在数组大于或小于中间元素的那一半中继续查找,每次查找都从中间元素开始比较。这样,每一次比较都能使搜索范围缩小一半,因此它是一种效率较高的查找方法。

使用折半查找的前提是对有序数组进行查找,其主要应用场景是查找数组中某个切实存在的数字,也可以稍微变化一些应用场景,如查找有序的字符数组中的某个字符,或者是查找某个数值所在的区间。

折半查找的过程包括建立要查找的有序数组,定义起点、中间点、终点变量和要查找的常量,然后进入查找循环,编写查找逻辑。如果在某一步骤数组为空,则代表找不到目标元素。

折半查找的效率

折半查找(二分查找)的效率非常高,其时间复杂度为O(log n),其中n是数组中的元素数量。这是因为每次查找都能将搜索范围缩小一半,所以查找次数与数组大小的对数成正比。这种高效的查找效率使得折半查找在处理大型有序数组时特别有用。

然而,值得注意的是,折半查找的前提是数组必须是有序的。如果数组无序,那么折半查找将无法进行,此时需要使用其他查找算法,如顺序查找。此外,虽然折半查找的查找效率很高,但其插入和删除操作的效率却相对较低,因为需要保持数组的有序性。

在实际应用中,如果数据量大且经常需要进行查找操作,且可以预先对数据进行排序,那么使用折半查找将是非常合适的选择。然而,如果数据量较小,或者数据的插入和删除操作频繁,那么可能需要考虑使用其他数据结构或算法来平衡查找和更新操作的效率。

4. 分块查找

分块查找,也称为块查找或索引顺序查找,是一种查找算法。它是折半查找和顺序查找的一种改进方法,特别适合于节点动态变化的情况。

分块查找的基本思想是将数据划分为多个块,并对每个块进行排序。每个块内的数据元素有序排列,而块与块之间是有序的,即第i+1块的所有记录关键字均大于(或小于)第i块记录关键字。在查找时,首先确定待查记录所在块,再在块内进行顺序查找。

分块查找的优点在于,由于只要求索引表是有序的,对块内节点没有排序要求,因此可以跳过一些不必要的块,从而提高查找效率。然而,由于需要预处理数据集,因此在数据集经常变化的情况下,它的效率可能会降低。因此,分块查找更适用于数据较多但数据不会发生变化的情况。

总之,分块查找结合了顺序查找和二分查找的优点,使得在大规模数据集中进行查找更加高效。

- 理解

  1. 折半查找过程对应的判定树一定是一棵平衡二叉树

  2. 折半查找和二叉排序树的性能比较

    1. 折半查找是二叉排序树最好的情况,复杂度O(log₂n)

    2. 二叉排序树如果形成单树,则与顺序查找相似,复杂度O(n)

  3. 对于一个长度为n的有序顺序表,如果采用折半查找一个不存在的元素,比较次数最多即为树高【log₂(n+1)】,最少即为树高减去1

  4. 计算折半查找平均失败查找时间,每个失败点的比较次数即为该点父节点的高度,即为该结点高度减一

  5. 判断空白二叉树是否是折半二叉树的办法

    1. 按照排序二叉树规则,从小到大为各空白结点标上数字

    2. 根据折半规则,判断每个树是向上折半取整还是向下折半取整、

    3. 判断各根节点是否符合折半规则、取整规则

      1. 向上取整都是优先排在左边,左子树比右子树最多多一个结点

      2. 向下取整都是优先排在右边,右子树比左子树最多多一个结点

- 技巧

  1. 顺序查找,无论是有序表还是无序表,平均查找时间相同

  2. 折半查找的判定树是一棵二叉排序树,因此,给出一定的比较值序列,如果不满足二叉排序树的规则(左<根<右)则不是折半的比较序列

这篇关于数据结构——7.17.2 查找的基本概念、顺序查找和折半查找的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【机器学习】高斯网络的基本概念和应用领域

引言 高斯网络(Gaussian Network)通常指的是一个概率图模型,其中所有的随机变量(或节点)都遵循高斯分布 文章目录 引言一、高斯网络(Gaussian Network)1.1 高斯过程(Gaussian Process)1.2 高斯混合模型(Gaussian Mixture Model)1.3 应用1.4 总结 二、高斯网络的应用2.1 机器学习2.2 统计学2.3

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹

Verybot之OpenCV应用二:霍夫变换查找圆

其实我是想通过这个程序来测试一下,OpenCV在Verybot上跑得怎么样,霍夫变换的原理就不多说了,下面是程序: #include "cv.h"#include "highgui.h"#include "stdio.h"int main(int argc, char** argv){cvNamedWindow("vedio",0);CvCapture* capture;i

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre