给定一个值K,在含有n个记录的文件中进行搜索,寻找一个关键值等于K的记录,如找到则输出该记录,负责输出查找不成功的信息。
静态查找表
1、顺序查找
用逐一比较的办法顺序查找关键字。
- 性能分析:顺序查找平均查找长度为(n+1)/2,时间效率为O(n)
- 优点:算法简单、适应面广,对查找表的结构没有要求,无论记录是否按关键字有序排列均可使用。
缺点:在n值较大时,平均查找长度较大,查找效率较低。
2、折半查找(二分查找)
先给数据排序,形成有序表,把待查数据值与查找范围的中间元素值进行比较,会有四种情况出现:
1)待查找数值与中间元素值相等,返回中间元素值的索引。
2)待查找数值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围,执行1),直到找到相等的值。
3)待查找数值比中间元素值大,则以整个查找范围的后半部分作为新的查找范围,执行1),直到找到相等的值
4)如果最后找不到相等的值,则返回错误提示信息。
折半查找比顺序查找效率高
3、分块查找
又称索引顺序查找,是对顺序查找方法的一种改进,其性能介于顺序查找和折半查找之间。
在分块查找过程中,首先把表分成若干块,每一块中的关键字不一定有序,但块之间是有序的,即后一块中所有记录的关键字均大于前一块中最大的关键字,还建立了一个索引表,索引表按关键字有序。
分块查找示意图
哈希表
是根据关键码值(Key value)而直接进行访问的数据结构。由关键码的值决定数据的存储地址,以加快查找速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
优点:查找速度极快(O(1)),查找效率与元素个数n无关!
网友评论