Ⅳ. 查找算法(Search Algorithm)

2018-06-07  本文已影响0人  執著我們的執著

查找算法

定义:
查找算法的分类
平均查找长度(Average Search Length,ASL):

常见的查找(搜索)算法


1. 顺序查找

基本思想 : 属于无序查找算法,从数据表的一端顺序扫描,依次将数据元素的关键值与给定值Value比较,直至找到相等的表示成功,或扫描结束仍未找到,表示失败;

复杂度分析

代码后补

2. 二分查找(折半查找)

基本思想数据表必须为有序表,属于有序查找算法;如果数据表原本无序,则先要进行排序操作;
给定值为Value,与数据表中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据Value与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归下去,直到查找到或查找结束发现表中没有这样的结点。

[注] 折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据表来说,维护有序的排序会带来不小的工作量,不建议使用。

复杂度分析

代码后补

3. 分块查找(也称为索引查找)

分块查找的数据表的特点 : 分块有序 即[ 块间有序,块内无序]

分块示例

基本思想 :将一个 n 个数据元素的数据表"按块有序"划分为 m 块(m<=n),每个块中元素关键字不必有序,但块与块之间必须"按块有序"; 第 1 个块中的任一元素的关键字小于第 2 个块中的任一元素的关键字(或大于),第 2 个块中的任一元素的关键字小于第 3 个块中的任一元素的关键字(或大于)... ...

分块算法流程

代码后补
上一篇 下一篇

猜你喜欢

热点阅读