高中二年级下学期信息科技《查找》教学课件.pptx

5.2查找

5.2查找1、查找的意义信息学是处理大量信息的学科。除了对于收集到的信息转为数据进行处理和存储外，一个重要的需求就是对存储的数据进行查找。日常生活中，我们就经常进行查找工作，例如在图书馆中查找图书、在字典中查找汉字等。如果将图书目录、字典等视作一张表，查找则是在一个含有众多数据元素的表中找出某个特定的数据元素。在信息时代，由于信息量巨大，人工查找非常困难，因此需要依赖于计算机快速准确地查找信息

5.2查找1、查找的意义顺序表是指采用顺序存储的方式存储的集合或线性表。本节所讨论的两种查找方法，均是针对一维数组这种顺序表的查找方法。

5.2查找2、顺序查找顺序查找又称线性查找。顺序查找的基本思想： 从顺序表的一端开始，依次将每个元素的关键字与给定值k进行比较，如果相同，则查找成功，返回该元素的下标；如果所有元素比较后仍然找不到关键字为k的元素，则查找失败，返回特定值-1。

5.2查找2、顺序查找例如，要实现查询超市中某个商品在哪个货架，可以用数组存储商品的编号、存放的货架等信息。程序运行时，输入需查询商品的编号，然后在数组中依次查找编号，即可根据编号对应的下标提取出商品的信息。

5.2查找2、顺序查找intsearch(ShangPinTypea[],intk,intn){ //在有n个元素的数组a中查找编号k。 for(inti=0;in;i++) if(k==a[i].Bianhao)returni; //查找成功，返回商品对应的数组下标。 return-1; //查找失败，返回-1}

5.2查找3、二分查找顺序查找的思想易于理解，但其缺点也很明显： 如果商品的数量过多，顺序查找每次都需要在数组中从头到尾依次查找，消耗大量时间。因此，为了加快查找的速度，可以使用另一种查找方式：二分查找。

5.2查找3、二分查找二分查找，又称折半查找。适用于顺序存储的有序表（各元素按关键字的值升序或降序存放的表）进行的查找。二分查找的思想： 利用有序表的有序性，每次将待查找元素所处的可能区间范围缩小一半，以达到快速定位查找元素的目的。 通过每次比较当前范围的中间元素与待查找元素的相对大小，可以确定待查找元素位于当前区间的左侧还是右侧。

5.2查找3、二分查找以升序存储的有序表a为例，二分查找的主要思路如下：（1）设定当前的查找范围l=0,r=n-1。（2）选定查找范围的中点元素mid=(l+r)/2，与k值比较 （a）若k==a[mid]，则查找成功，返回该元素的下标 （b）若ka[mid]，则将范围缩小到左子表a[l]~a[mid-1] （c）若ka[mid]，则将范围缩小到右子表a[mid+1]~a[r]（3）迭代上述过程，直到找到k或当前查找区间为空（查找失败）

5.2查找intbinsearch(ShangPinTypea[],intk,intn){ //在n个元素的升序表a中二分查找k intl=0,r=n-1; //初始化查找范围的下界与上界 while(l=r) //终止条件为查找范围为空，即lr { intmid=(l+r)/2; //取出中间元素下标 if(k==a[mid].BianHao)returnmid; //查找成功 elseif(ka[mid].BianHao)r=mid-1; //如果没有找到且编号偏小，则修改上界前往左子表 elsel=mid+1; //否则修改下界前往右子表。 } return-1; //查找范围为空时仍未找到，则查找失败。}

5.2查找3、二分查找例：假设一维升序数组a中有10个元素：1,2,6,8,12,13,36,45,49,85。现模拟查找k=45的二分查找过程： 下标：0123456789 元素：1268121336454985 LRMid

5.2查找3、二分查找例：假设一维升序数组a中有10个元素：1,2,6,8,12,13,36,45,49,85。现模拟查找k=45的二分查找过程： 下标：0123456789 元素：1268121336454985 LRMidLMid

5.2查找3、二分查找例：假设一维升序数组a中有10个元素：1,2,6,8,12,13,36,45,49,85。现模拟查找k=48的二分查找过程： 下标：0123456789 元素：126812133645