第七章第一节：顺序查找和折半查找

教程

1. 查找

2. 顺序查找：

3. 折半查找

4. 分块查找：

1. 查找的基本概念

查找——在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找表（查找结构)——用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。
关键字——数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

---

---

1.1 对查找表的常见操作

1.2 查找算法的评价指标

查找长度——在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度(ASL, Average Search Length)——所有查找过程中进行关键字的比较次数的平均值。

ASL的数量级反应了查找算法时间复杂度

---

---

---

2. 顺序查找

2.1 顺序查找的算法思想

顺序查找，又叫“线性查找”，通常用于线性表。
算法思想:从头到jio 挨个找(或者反过来也OK)

2.2. 顺序查找的实现

typedef struct{    //查找表的数据结构(顺序表)
    ElemType *elem;  //动态数组基址
    int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for( i=0; i<ST.TableLen && ST.elem[i] !=key; ++i);//查找成功，则返回元素下标;查找失败，则返回-1
return i==ST.TableLen? -1 : i;
}

1
2
3
4
5
6
7
8
9
10
11

---

2.3 查找效率分析

---

2.4 顺序查找的优化（对有序表）

---

2.5 用查找判定树分析ASL

• 一个成功结点的查找长度=自身所在层数
• 一个失败结点的查找长度=其父节点所在层数
• 默认情况下，各种失败情况或成功情况都等概率发生

2.6 顺序查找的优化（被查概率不相等）

3. 折半查找

折半查找，又称“二分查找”，仅适用于有序的顺序表

3.1 折半查找的算法思想

折半查找的基本思想:

首先将给定值key与表中中间位置的元素比较,若相等，则查找成功，返回该元素的存储位置;若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如，在查找表升序排列时，若给定值key大于中间元素，则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

3.2 折半查找的算法实现

3.3 查找判定树（重要 ）

---

---

---

---

3.4 查找效率分析

查找成功：

3.5 总结

---

---

4. 分块查找（选择题）

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

4.1 分块查找的算法思想

分块查找的基本思想:

将查找表分为若干子块。块内的元素可以无序，但块之间是有序的即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找，又称索引顺序查找，算法过程如下:

①在索引表中确定待查记录所属的分块(可顺序、可折半)
②在块内顺序查找

4.2 查找效率分析（ASL）

例如,关键码集合为{88,24,72,61,21,6,32,11,8,31,22,83,78,54},按照关键码值24,54,78,88,分为4个块和索引表，
如图7.3所示;

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均杏找长度分别为L,Ls，则分块查找的平均查找长度为

4.3 总结