网站网站建设考虑要素,企业网络安全管理,组织建设内容,浙江产品设计公司7.17.2 查找的基本概念、顺序查找和折半查找
1. 基本概念
1. 关键字#xff1a;数据元素中标识该元素的某个数据项的值#xff0c;使用基于关键字的查找#xff0c;查找结果应该是唯一的。2. 查找表的常见操作1. 查找符合条件的数据元素#xff1a;查得快即可2. …7.17.2 查找的基本概念、顺序查找和折半查找
1. 基本概念
1. 关键字数据元素中标识该元素的某个数据项的值使用基于关键字的查找查找结果应该是唯一的。2. 查找表的常见操作1. 查找符合条件的数据元素查得快即可2. 插入、删除某个数据元素兼顾查找速度和操作便捷3. 查找算法的评价指标1. 查找长度——在查找运算中需要对比关键字的次数称为查找长度2. 平均查找长度(ASL,Average Search Length)——所有查找过程中进行关键字的比较次数的平均值2. 顺序查找
也称线性查找即遍历常用于线性表顺序、链表
顺序查找是一种简单的查找方式。这种查找方法从列表的一端开始顺序搜索直到找到所需的元素为止。
顺序查找的基本思想是从列表的第一个元素开始逐个检查每个元素直到找到所需的元素或搜索到列表的末尾为止。
顺序查找的步骤如下
从列表的第一个元素开始与所要查找的元素进行比较。如果相等则查找成功返回该元素在列表中的位置。如果不相等则继续向后查找下一个元素。重复以上步骤直到找到所需元素或搜索到列表的末尾。
顺序查找的时间复杂度是O(n)其中n是列表中元素的数量。这是因为在最坏的情况下可能需要检查列表中的每个元素。虽然顺序查找在某些情况下可能不是最高效的查找方法但它简单易懂适用于小型列表或对效率要求不高的场景。
优化思路将大概率要被查询的值放到前面来该方法适用于经常需要查询的情况
顺序查找虽然简单易懂但在处理大型数据集时效率较低。为了优化顺序查找的性能可以考虑以下几种方法 减少比较次数 预处理数据在搜索前对数据进行排序可以减少平均情况下的比较次数。虽然排序本身需要时间但对于多次查找的情况排序可能是一个值得的预处理步骤。利用数据的特性如果数据具有某种模式或分布可以设计更高效的查找策略。 使用哨兵或标记 在列表的末尾添加一个哨兵值或标记这样当查找的元素不存在时可以更快地停止查找。 分块查找 将列表分成多个块每个块内部可以是无序的但块之间是有序的。首先确定目标元素可能存在的块然后在该块内进行顺序查找。这种方法结合了顺序查找和索引查找的优点。 使用更好的数据结构 如果可能的话使用更高效的数据结构如哈希表、二分查找树等来存储和查找数据。这些数据结构提供了更快的查找时间复杂度。 并行化 在多核处理器或多计算机环境下可以并行地进行查找操作。将数据分割成多个部分每个部分由一个处理单元同时搜索。 缓存优化 对于顺序访问的列表确保数据在物理内存中是连续的以减少缓存未命中的次数。 算法层面的优化 使用更高效的比较算法比如对于大型整数或浮点数可以使用更快速的比较方法。
需要注意的是优化顺序查找的性能通常需要根据具体的应用场景和数据特点来选择合适的方法。在某些情况下优化可能并不总是值得的因为可能会增加代码的复杂性和维护成本。因此在进行优化之前需要仔细评估需求和性能要求并确定最合适的优化策略。
3. 折半查找
折半查找又称“二分查找”仅适用于有序的顺序表这是因为顺序表具有随机存储的特性而链表没有
折半查找是一种在有序数组中查找某一特定元素的搜索算法。其基本原理是从数组的中间元素开始如果中间元素正好是要查找的元素则搜索过程结束如果某一特定元素大于或小于中间元素则在数组大于或小于中间元素的那一半中继续查找每次查找都从中间元素开始比较。这样每一次比较都能使搜索范围缩小一半因此它是一种效率较高的查找方法。
使用折半查找的前提是对有序数组进行查找其主要应用场景是查找数组中某个切实存在的数字也可以稍微变化一些应用场景如查找有序的字符数组中的某个字符或者是查找某个数值所在的区间。
折半查找的过程包括建立要查找的有序数组定义起点、中间点、终点变量和要查找的常量然后进入查找循环编写查找逻辑。如果在某一步骤数组为空则代表找不到目标元素。
折半查找的效率
折半查找二分查找的效率非常高其时间复杂度为O(log n)其中n是数组中的元素数量。这是因为每次查找都能将搜索范围缩小一半所以查找次数与数组大小的对数成正比。这种高效的查找效率使得折半查找在处理大型有序数组时特别有用。
然而值得注意的是折半查找的前提是数组必须是有序的。如果数组无序那么折半查找将无法进行此时需要使用其他查找算法如顺序查找。此外虽然折半查找的查找效率很高但其插入和删除操作的效率却相对较低因为需要保持数组的有序性。
在实际应用中如果数据量大且经常需要进行查找操作且可以预先对数据进行排序那么使用折半查找将是非常合适的选择。然而如果数据量较小或者数据的插入和删除操作频繁那么可能需要考虑使用其他数据结构或算法来平衡查找和更新操作的效率。
4. 分块查找
分块查找也称为块查找或索引顺序查找是一种查找算法。它是折半查找和顺序查找的一种改进方法特别适合于节点动态变化的情况。
分块查找的基本思想是将数据划分为多个块并对每个块进行排序。每个块内的数据元素有序排列而块与块之间是有序的即第i1块的所有记录关键字均大于或小于第i块记录关键字。在查找时首先确定待查记录所在块再在块内进行顺序查找。
分块查找的优点在于由于只要求索引表是有序的对块内节点没有排序要求因此可以跳过一些不必要的块从而提高查找效率。然而由于需要预处理数据集因此在数据集经常变化的情况下它的效率可能会降低。因此分块查找更适用于数据较多但数据不会发生变化的情况。
总之分块查找结合了顺序查找和二分查找的优点使得在大规模数据集中进行查找更加高效。
- 理解 折半查找过程对应的判定树一定是一棵平衡二叉树 折半查找和二叉排序树的性能比较 折半查找是二叉排序树最好的情况复杂度O(log₂n) 二叉排序树如果形成单树则与顺序查找相似复杂度O(n) 对于一个长度为n的有序顺序表如果采用折半查找一个不存在的元素比较次数最多即为树高【log₂(n1)】最少即为树高减去1 计算折半查找平均失败查找时间每个失败点的比较次数即为该点父节点的高度即为该结点高度减一 判断空白二叉树是否是折半二叉树的办法 按照排序二叉树规则从小到大为各空白结点标上数字 根据折半规则判断每个树是向上折半取整还是向下折半取整、 判断各根节点是否符合折半规则、取整规则 向上取整都是优先排在左边左子树比右子树最多多一个结点 向下取整都是优先排在右边右子树比左子树最多多一个结点
- 技巧 顺序查找无论是有序表还是无序表平均查找时间相同 折半查找的判定树是一棵二叉排序树因此给出一定的比较值序列如果不满足二叉排序树的规则左根右则不是折半的比较序列
