中小学教育资源及组卷应用平台
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
第三课时 采用索引查找法查找商品
教材分析
本节的主要内容是采用索引查找法查找商品。在学习中，学生将体验使用二分查找法查找对应价格的商品数据。本项目的学习强调引导学生对实际问题从数据量大小、运行时间、存储空间和算法实现难易度等方面进行综合考虑，选择恰当的查找算法，使用合适的存储结构,通过编程实现问题的解决。在体验使用二分查找法查找商品的过程中,分别采用迭代法和递归法来完成算法设计，进一步提升计算思维。索引查找法虽然有一定难度，但是有助于学生进一步认识算法与数据结构的关系，从而进一步提升计算思维。
教学目标
1.掌握常用的数据查找方法——索引查找法；
2.理解迭代概念。
3.理解递归概念。
4.进一步理解算法与数据结构的关系。
5.培养学生的信息意识和计算思维能力。
教学重点
1.掌握常用的数据查找方法、理解迭代和递归概念；
2.进一步理解算法与数据结构的关系。
教学难点
1.进一步理解算法与数据结构的关系；
2.培养学生的信息意识和计算思维能力。
教学方法
体验法、讲授法、讨论法、示例法
教学准备
计算机教室、多媒体设备、多媒体广播软件、Python编程环境、待查找的商品价格数据、教学课件等。
教学过程
一、新课导入
复习前面学习的查找算法：顺序查找法、二分查找法。
哪还有比这更好的查找方法吗？
引出课题——索引查找法。
二、索引查找法
1.核心概念
索引查找是在索引表和主表(即线性表的索引存储结构 ( https: / / baike. / doc / 6059445-6272495.html" \t "https: / / baike. / doc / _blank ))上进行的查找。
2.查找过程
①首先根据给定的索引值K1，在索引表上查找出索引值等于KI的索引项，以确定对应予表在主表中的开始位置和长度，
②然后再根据给定的关键字K2，茬对应的子表中查找出关键字等于K2的元素(结点)。对索引表或子表进行查找时，若表是顺序存储的有序表，则既可进行顺序查找，也可进行二分查找，否则只能进行顺序查找。
3.索引的分类
在线性索引中，我们重点介绍三种：稠密索引、分块索引和倒排索引。
①稠密索引
首先是稠密索引。稠密索引是指在线性表中，将数据集中的每个记录对应一个索引项。就像我们上面示例图中的那样。以主键为例，可以将其抽象化如下：
对于稠密索引这个索引表来说，索引项一定按照关键码有序排列，这样可以应用二分查找，以免索引查找本身影响性能。可见，稠密索引性能可以做到和二分查找相当（找到对应关键码就可以通过指针直接指向对应记录），但是索引项长度和数据集一样长，空间复杂度高，如果数据太多需要存放到磁盘上，反复读取磁盘对性能影响很大。
因此，我们又引入了分块索引。
②分块索引
为了减少索引项个数，我们对数据集进行分块，并使其分块有序，然后再给每个分块建立一个索引项（索引值是分块中最大关键码），至于分块内部，则不管其有序性，从而减少索引项的个数。在查找的时候在索引项中通过二分查找找到指定索引项，然后根据该索引项中的关键码去相应分块遍历查找指定元素，这是一种折中方案，既兼顾了空间复杂度，又兼顾了时间复杂度。
分块索引图示如下：
这里面有几个概念需要阐述下，首先是分块有序，需要满足两个先决条件：
块内无序。即每一块内的记录不要求有序。当然，有序更理想，只不过要花费大量时间和空间的代价。
块间有序。即要求后一块的所有关键字都大于前一块的所有关键字。只有块间有序，才能给查找带来效率。
其次，分块索引的索引项包含三个数据项：
最大关键码：它存储每一块中的最大关键字。这样做的好处是在它之后的下一块中最小的关键字也能比这一块最大的关键字要大。
块长：存储块中的记录个数，以便于循环时使用。
块首指针：用于指向块首数据元素的指针，便于开始对这一块的记录开始遍历。
最后，在分块索引中查找，分两块进行：
在分块索引表中查找要查找关键字所在的块。由于块间有序，所以可以通过二分查找快速定位（通过不小于给定值的第一个元素，不大于给定值的最后一个元素确定区间，以前面给出的示例图为例，58位于57和96之间，则会去第三块中查找）。
根据块首指针找到相应的块，并在块中顺序查找指定值（即关键码，块中无序所以只能顺序查找）。
③倒排索引
百度、Google 等搜索引擎为我们日常查找信息带来了巨大的方便，你是否思考过搜索引擎是如何从海量 HTML 文档中通过关键词查找资源的？给大家介绍最简单，也是最基础的搜索引擎技术 —— 倒排索引。
有倒排索引，就有正向索引，正向索引指的是通过文档 ID 找到对应的文档，如果通过文档ID查找对应文档，再在文档中匹配关键词，意味着要扫描所有文档，最后还要排序，对于互联网上的海量资源来说，显然是不可取的。
所以搜索引擎反其道行之，通过分析每个文档，提取其中的关键字，并建立关键词与文档 ID 的映射关系，每个关键词都对应着多个文档 ID。由于不是通过文档来确定属性（这里的属性是关键词），而是通过属性来确定文档，故而将其称作倒排索引。
在涉及中文的文章中，还要进行中文分词。
三、采用索引查找法查找商品
假设要在大量价格无序的商品中，查找价格为22的商品。可以通过建立索引表的方式在找，如图5-13所示。
查找表：
图5-13索引表
其中，索引表由索引项组成。索引表中的每一个索引项都包含两项内容，一项是子表的特征值(索引值)，另一项是地址(子表在主表中的开始位置)。例如，索引项(210)表示小于等于21的序列(子表1)在数据表中的开始位置是0,索引项(40 5)表示小于等于40大于21的序列(子表2)在查找表中的开始位置是5，以此类推。查找22时，先在索引表中查找到索引项(40 5)，再在查找表中的子表2中从第一个位置开始查找，直到找到2。查找时，总共比较5次。
子表(也称块)一般根据特征值划分。图中子表的子表里的所有数据都小于下一个子表里的所有数据。特征值是该子表里的最大数。
思考与讨论？
1.上述第二个索引项的特征值是否可以选33 为什么？如果选33,那么子表2该如何划分？
可以。子表2划分到第8项25。
2.索引查找法对主表有什么要求？
通常适用于数据量较大的主表。
四、分析查找算法与数据结构的关系
使用不同查找法查找一个数据元素的比较次数是不同的，我们可以用平均查找次数来衡量查找的速度。例如，顺序查找法的平均查找次数是(1+2+…+n)/n，其中，n代表元素个数，括号内的每一项代表查找第1个元素的比较次数，利用求和公式可以得平均查找次数为(1+n)/2,可见该平均查找次数与查找序列元素的个数成正比。而采用索引存储结构的索引查找法查找次数与主表的数据元素的个数几乎是无关的。因此，数据量大的情况下，采用索引查找法查找的算法效率会高很多。但是采用索引存储结构来存储须附加存储索引表，因此会占用更多的存储空间。
小贴士
一个算法是由控制结构(顺序、分支和循环)和固有数据类型的操作构成的。算法执行时间取决于两者的综合效果，是衡量算法效率的一个方面。算法执行时间与基本操作次数成正比。
思考与讨论？
1.若使用二分查找法，查找每个数据元素的比较次数分别是多少？
平均查找次数：
Log2(n+1)-1
最多查找次数：
Int(Log2n)+1
2.二分查找法和顺序查找法的查找速度哪个快？为什么？
当数据达到一定规模的时候，二分查找的查找速度明显比顺序查找快。因为二分查找法每次将查找区间缩小一半，所以需要比较的次数要少很多。
五、课堂活动
1.对于以下价格序列的商品，若采用索引查找法，请为其建立索引表，查找38并计算比较次数，谈谈索引查找的好处。1,6,8,9,7,27,13,15,64,55,44,42,38,78,90,66
参考答案：
索引表：
先在索引表中查找到索引项(64 8)，再在查找表中的子表3中从第一个位置开始查找，直到找到38,总共比较8次。
索引表是有序的，可以二分查找索引项。找到后,根据地址找到主表中的子表开始位置开始查找,查找范围缩小为子表。在数据量大的情况下,采用索引存储可大幅提高查找速度。
2.查阅资料，根据所学，归纳表中各查找算法分别适合何种存储结构，并给出理由，谈谈数据结构和算法之间的关系。
算法 顺序存储结构 链式存储结构 索引存储结构
二分查找
顺序查找
索引查找
参考答案：
算法 顺序存储结构 链式存储结构 索引存储结构
二分查找 √
顺序查找 √ √
索引查找 √
二分查找必须使用顺序存储结构。
顺序查找可以使用顺序存储结构，也可以使用链式存储结构。
索引存储中的索引表是有序的，可以顺序查找，也可以二分查找。
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)(共42张PPT)
第三课时 采用索引查找法查找商品
信息技术沪教版 选择性必修1
第五单元 排序与查找
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
一、新课导入
二、索引查找法
三、采用索引查找法查找商品
四、分析查找算法与数据结构的关系
五、课堂活动
一、新课导入
1.复习顺序查找算法
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在，最原始的方法是从头到尾挨个查找，这种查找的方法叫顺序查找方法。
2.复习二分查找算法
迭代法：用计算机解决问题的一种基本方法。是一种不断用变量的旧值递推出新值的过程，常用于重复性操作。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
哪还有比这更好的查找方法吗？
二、索引查找法
1.核心概念
索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找。
2.查找过程
①首先根据给定的索引值K1，在索引表上查找出索引值等于KI的索引项，以确定对应予表在主表中的开始位置和长度，
②然后再根据给定的关键字K2，茬对应的子表中查找出关键字等于K2的元素(结点)。对索引表或子表进行查找时，若表是顺序存储的有序表，则既可进行顺序查找，也可进行二分查找，否则只能进行顺序查找。
3.索引的分类
01
02
03
03
倒排索引
02
分块索引
01
稠密索引
3.索引的分类
01
稠密索引
稠密索引是指在线性表中，将数据集中的每个记录对应一个索引项。就像我们上面示例图中的那样。以主键为例，可以将其抽象化如下：
3.索引的分类
01
稠密索引
对于稠密索引这个索引表来说，索引项一定按照关键码有序排列，这样可以应用二分查找，以免索引查找本身影响性能。可见，稠密索引性能可以做到和二分查找相当（找到对应关键码就可以通过指针直接指向对应记录），但是索引项长度和数据集一样长，空间复杂度高，如果数据太多需要存放到磁盘上，反复读取磁盘对性能影响很大。
因此，我们又引入了分块索引。
3.索引的分类
02
分块索引
为了减少索引项个数，我们对数据集进行分块，并使其分块有序，然后再给每个分块建立一个索引项（索引值是分块中最大关键码），至于分块内部，则不管其有序性，从而减少索引项的个数。在查找的时候在索引项中通过二分查找找到指定索引项，然后根据该索引项中的关键码去相应分块遍历查找指定元素，这是一种折中方案，既兼顾了空间复杂度，又兼顾了时间复杂度。
3.索引的分类
02
分块索引
分块索引图示如下：
3.索引的分类
02
分块索引
即要求后一块的所有关键字都大于前一块的所有关键字。只有块间有序，才能给查找带来效率。
块间有序
即每一块内的记录不要求有序。当然，有序更理想，只不过要花费大量时间和空间的代价。
块内无序
需要满足两个先决条件
3.索引的分类
02
分块索引
03
02
01
最大关键码
它存储每一块中的最大关键字。这样做的好处是在它之后的下一块中最小的关键字也能比这一块最大的关键字要大。
块长
存储块中的记录个数，以便于循环时使用。
块首指针
用于指向块首数据元素的指针，便于开始对这一块的记录开始遍历。
3.索引的分类
02
分块索引
在分块索引表中查找要查找关键字所在的块。由于块间有序，所以可以通过二分查找快速定位（通过不小于给定值的第一个元素，不大于给定值的最后一个元素确定区间，以前面给出的示例图为例，58位于57和96之间，则会去第三块中查找）。
根据块首指针找到相应的块，并在块中顺序查找指定值（即关键码，块中无序所以只能顺序查找）。
3.索引的分类
03
倒排索引
百度、Google 等搜索引擎为我们日常查找信息带来了巨大的方便，你是否思考过搜索引擎是如何从海量 HTML 文档中通过关键词查找资源的？给大家介绍最简单，也是最基础的搜索引擎技术 —— 倒排索引。
3.索引的分类
03
倒排索引
有倒排索引，就有正向索引，正向索引指的是通过文档 ID 找到对应的文档，如果通过文档ID查找对应文档，再在文档中匹配关键词，意味着要扫描所有文档，最后还要排序，对于互联网上的海量资源来说，显然是不可取的。
所以搜索引擎反其道行之，通过分析每个文档，提取其中的关键字，并建立关键词与文档 ID 的映射关系，每个关键词都对应着多个文档 ID。由于不是通过文档来确定属性（这里的属性是关键词），而是通过属性来确定文档，故而将其称作倒排索引。
三、采用索引查找法查找商品
假设要在大量价格无序的商品中，查找价格为22的商品。可以通过建立索引表的方式在找，如图所示。
其中，索引表由索引项组成。索引表中的每一个索引项都包含两项内容，一项是子表的特征值(索引值)，另一项是地址(子表在主表中的开始位置)。例如，索引项(210)表示小于等于21的序列(子表1)在数据表中的开始位置是0,索引项(40 5)表示小于等于40大于21的序列(子表2)在查找表中的开始位置是5，以此类推。查找22时，先在索引表中查找到索引项(40 5)，再在查找表中的子表2中从第一个位置开始查找，直到找到2。查找时，总共比较5次。
小贴士
子表(也称块)一般根据特征值划分。图中子表的子表里的所有数据都小于下一个子表里的所有数据。特征值是该子表里的最大数。
思考与讨论
1.上述第二个索引项的特征值是否可以选33 为什么？如果选33,那么子表2该如何划分？
思考与讨论
1.上述第二个索引项的特征值是否可以选33 为什么？如果选33,那么子表2该如何划分？
可以。子表2划分到第8项25。
思考与讨论
2.索引查找法对主表有什么要求？
思考与讨论
2素引查找法对主表有什么要求？
通常适用于数据量较大的主表。
四、分析查找算法与数据结构的关系
使用不同查找法查找一个数据元素的比较次数是不同的，我们可以用平均查找次数来衡量查找的速度。例如，顺序查找法的平均查找次数是(1+2+…+n)/n，其中，n代表元素个数，括号内的每一项代表查找第1个元素的比较次数，利用求和公式可以得平均查找次数为(1+n)/2,可见该平均查找次数与查找序列元素的个数成正比。而采用索引存储结构的索引查找法查找次数与主表的数据元素的个数几乎是无关的。因此，数据量大的情况下，采用索引查找法查找的算法效率会高很多。但是采用索引存储结构来存储须附加存储索引表，因此会占用更多的存储空间。
小贴士
一个算法是由控制结构(顺序、分支和循环)和固有数据类型的操作构成的。算法执行时间取决于两者的综合效果，是衡量算法效率的一个方面。算法执行时间与基本操作次数成正比。
思考与讨论
1.若使用二分查找法，查找每个数据元素的比较次数分别是多少？
思考与讨论
1.若使用二分查找法，查找每个数据元素的比较次数分别是多少？
平均查找次数：
Log2(n+1)-1
最多查找次数：
Int(Log2n)+1
思考与讨论
2.二分查找法和顺序查找法的查找速度哪个快？为什么？
思考与讨论
2.二分查找法和顺序查找法的查找速度哪个快？为什么？
当数据达到一定规模的时候，二分查找的查找速度明显比顺序查找快。因为二分查找法每次将查找区间缩小一半，所以需要比较的次数要少很多。
五、课堂活动
1.对于以下价格序列的商品，若采用索引查找法，请为其建立索引表，查找38并计算比较次数，谈谈索引查找的好处。1,6,8,9,7,27,13,15,64,55,44,42,38,78,90,66
参考答案：
索引表：
先在索引表中查找到索引项(64 8)，再在查找表中的子表3中从第一个位置开始查找，直到找到38,总共比较8次。
索引表是有序的，可以二分查找索引项。找到后,根据地址找到主表中的子表开始位置开始查找,查找范围缩小为子表。在数据量大的情况下,采用索引存储可大幅提高查找速度。
2.查阅资料，根据所学，归纳表中各查找算法分别适合何种存储结构，并给出理由，谈谈数据结构和算法之间的关系。
算法 顺序存储结构 链式存储结构 索引存储结构
二分查找
顺序查找
索引查找
参考答案：
算法 顺序存储结构 链式存储结构 索引存储结构
二分查找 √
顺序查找 √ √
索引查找 √
参考答案：
二分查找必须使用顺序存储结构。
顺序查找可以使用顺序存储结构，也可以使用链式存储结构。
索引存储中的索引表是有序的，可以顺序查找，也可以二分查找。
谢谢
21世纪教育网（www.21cnjy.com) 中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php
