数据结构中的三种线性表查找算法详解

数据结构中的三种线性表查找算法详解

引用

CSDN

1.

https://m.blog.csdn.net/m0_73399576/article/details/144278139

线性表是数据结构中的基础且重要的一环，其查找方法直接影响数据处理的效率。本文将详细介绍三种基于线性表的查找算法：顺序查找、折半查找和分块查找，帮助读者理解它们的实现原理、时间复杂度以及适用场景。

一、顺序查找（Sequential Search）

顺序查找，也称线性查找，是一种简单直观的查找算法。其查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后仍未找到关键字和给定值相等的记录，则查找失败。

顺序查找不仅适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。

算法实现

• 顺序表：从表的最后一个元素起，依次比较元素值和给定值，若找到值与给定值相等的元素，则查找成功，返回该元素的序号。若查遍整个顺序表都没有找到，则查找失败，返回0。
• 链表：通过指针next来依次扫描每个元素，逐个检查每个节点的数据域，直到找到目标值或遍历完所有节点。

算法分析

• 时间复杂度：O(n)，其中n为线性表的长度。因为顺序查找需要扫描整个表，所以时间复杂度与表的长度成正比。
• 空间复杂度：O(1)，只需要一个辅助空间来存储当前查找的位置。

优缺点

• 优点：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可应用。
• 缺点：平均查找长度较大，查找效率较低，所以当n很大时，不宜采用顺序查找。

二、折半查找（Binary Search）

折半查找，也称二分查找，是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素要按关键字有序排列。

查找过程

• 从表的中间记录开始，将给定值和中间记录的关键字进行比较。
• 如果给定值和中间记录的关键字相等，则查找成功。
• 如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找。
• 重复以上操作，直到查找成功，或者在某一步中查找区间为空（即low>high），则代表查找失败。

算法实现

• 初始化查找区间的初值，low为1，high为表长。
• 当low小于等于high时，循环执行以下操作：
• 计算mid为low和high的中间值。
• 将给定值key与中间位置记录的关键字进行比较。
• 若相等则查找成功，返回中间位置mid。
• 若不相等则利用中间位置记录将表对分成前、后两个子表。（如果key比中间位置记录的关键字小，则high取为mid-1，否则low取为mid+1）
• 循环结束，说明查找区间为空，则查找失败，返回0。

算法分析

• 时间复杂度：O(logn)，其中n为线性表的长度。因为折半查找每一次查找比较都使查找范围缩小一半，所以时间复杂度与表的长度成对数关系。
• 空间复杂度：O(1)，只需要几个辅助变量来存储当前查找的位置和区间。

优缺点

• 优点：查找效率高，适用于大规模数据的查找。
• 缺点：要求线性表必须采用顺序存储结构，且表中元素要按关键字有序排列。

三、分块查找（Blocking Search）

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，将线性表分成若干块，块内的元素可以无序，但块间是有序的。即第一个块中的最大元素小于第二个块中的所有元素，第二个块中的最大元素小于第三个块中的所有元素，依此类推。

查找过程

• 先确定待查元素所在的块，可以顺序查找或折半查找块间元素（即索引表）。
• 在确定的块内再顺序查找待查元素。

算法分析

• 分块查找的时间复杂度取决于块间查找和块内查找的时间复杂度。
• 如果块间采用顺序查找，时间复杂度为O(s+t)，其中s为块间查找的比较次数，t为块内查找的比较次数。
• 如果块间采用折半查找，时间复杂度可以降低到O(logb+(t/b))，其中b为块数，t为线性表的长度。

优缺点

• 优点：结合了顺序查找和折半查找的优点，适用于元素较多且块内元素无序的情况。
• 缺点：需要额外的空间来存储索引表，且块的大小和分割方式会影响查找效率。

总结

综上所述，基于线性表的查找法有顺序查找、折半查找和分块查找三种。每种查找方法都有其适用的场景和优缺点，在实际应用中应根据具体需求和数据特点选择合适的查找方法。