37对分查找算法及程序实现.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《37对分查找算法及程序实现.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 37 查找 算法 程序 实现
- 资源描述:
-
1、32对分查找的过程对分查找的过程若若key为查找键,数组为查找键,数组d存放存放n个已按升序排序的数据。在使用个已按升序排序的数据。在使用对分查找时,把查找范围对分查找时,把查找范围i,j的中间位置上的数据的中间位置上的数据d(m)与查找键与查找键key进行比较,结果必然是如下三种情况之一:进行比较,结果必然是如下三种情况之一:(1)若若keyd(m),由与,由与(1)相同的理由,必须在新的范围相同的理由,必须在新的范围(m1,j)中继续查找。中继续查找。这样,除了出现情况这样,除了出现情况(2),在通过一次比较后,新的查找范围将,在通过一次比较后,新的查找范围将不超过上次查找范围的一半。不超
2、过上次查找范围的一半。中间位置数据中间位置数据d(m)的下标的下标m的计算方法:的计算方法:m(ij)2或或mfix(ij)/2)以规模为以规模为16的递增数组的递增数组d为例,观察对分查找的为例,观察对分查找的过程。要查找的数据过程。要查找的数据key为为37。3对分查找算法的表示对分查找算法的表示使用对分查找在数组变量使用对分查找在数组变量d中查找中查找key,用自然语言描述的,用自然语言描述的算法如下:算法如下:(1)(确定初始查找范围确定初始查找范围)i1,jn。(2)(是否能继续查找?是否能继续查找?)如果如果ij,那么转到,那么转到(4)。(3)(找不到找不到)输入出结果输入出结果
3、0,算法结束。,算法结束。(4)(计算中点位置计算中点位置)m(ij)2。(5)(相等?相等?)如果如果d(m)key,那么转到,那么转到(7)。(6)(修改查找范围修改查找范围)如果如果keyd(m),那么,那么jm1;否则;否则im1,转到,转到(2)。(7)(找到找到)输出结果输出结果m,算法结束。,算法结束。使用流程图描述对分查找的算法如下图所示:使用流程图描述对分查找的算法如下图所示:4对分查找算法程序的实现要点对分查找算法程序的实现要点(1)由于比较次数难以确定,所以用由于比较次数难以确定,所以用Do语句来实现循环;语句来实现循环;(2)在在Do循环体中用循环体中用If语句来判断查
4、找是否成功;语句来判断查找是否成功;(3)若查找成功则输出查找结果,并结束循环若查找成功则输出查找结果,并结束循环(Exit Do);(4)若查找不成功,则判断查找键在数组的左半区间还是若查找不成功,则判断查找键在数组的左半区间还是右半区间,从而缩小范围。右半区间,从而缩小范围。对分查找的程序结构如下对分查找的程序结构如下(升序序列升序序列):对分查找程序的基本框架:对分查找程序的基本框架:Private Sub Command1_Click()i 1:j n Do While i j m (i j)2 If d(m)Key Then 输出结果,退出查找输出结果,退出查找(代码略代码略)Els
5、eIf Key d(m)Then j m 1 Else i m 1 End If LoopEnd Sub5.查找次数的估算查找次数的估算 对规模为对规模为n的数组进行对分查找时,无论是否找到,至的数组进行对分查找时,无论是否找到,至多进行多进行 log2n1(log2n表示大于或等于表示大于或等于 log2n的最小整数的最小整数)次次查找就能得到结果,而使用顺序查找算法,在最坏的情况下查找就能得到结果,而使用顺序查找算法,在最坏的情况下(查找键在最后一个或没找到查找键在最后一个或没找到),需要进行,需要进行n次查找,最好的次查找,最好的情况是一次查找情况是一次查找(查找键在第一个查找键在第一个
6、),平均查找次数是,平均查找次数是 。21n本节的学习要求掌握对分查找算法的基本思想,掌本节的学习要求掌握对分查找算法的基本思想,掌握对分查找算法的程序实现要点,学会编写简单的对分握对分查找算法的程序实现要点,学会编写简单的对分查找的程序。掌握对顺序查找与对分查找次数的估算。查找的程序。掌握对顺序查找与对分查找次数的估算。对分查找算法在历次考试中出现的概率为对分查找算法在历次考试中出现的概率为90%以上,考以上,考查方式为选择题与填空题。查方式为选择题与填空题。1下列有关查找的说法,正确的是下列有关查找的说法,正确的是 ()A顺序查找时,被查找的数据必须有序顺序查找时,被查找的数据必须有序 B
7、对分查找时,被查找的数据不一定有序对分查找时,被查找的数据不一定有序C顺序查找总能找到要查找的关键字顺序查找总能找到要查找的关键字 D一般情况下,对分查找的效率较高一般情况下,对分查找的效率较高D D 2某网站报名参加免费三亚游的会员序列号有:某网站报名参加免费三亚游的会员序列号有:101、135、238、342、450、558、633、708、846、910。采用对分查。采用对分查找,查找序列号为找,查找序列号为846号网友信息的过程中,依次被访问号网友信息的过程中,依次被访问的序列号是的序列号是()A450、708、846 B450、708、910、846C558、708、846 D558
8、、708、910、846A A3某电子图书馆网站有某电子图书馆网站有10万本图书记录万本图书记录(已索引排序已索引排序),假设,假设从中取出一条记录并与待查找项进行比较所花时间为从中取出一条记录并与待查找项进行比较所花时间为10毫毫秒,则用对分法在该系统中查找任意一本指定图书最多花秒,则用对分法在该系统中查找任意一本指定图书最多花费的时间约为费的时间约为()A100万毫秒万毫秒 B50万毫秒万毫秒C10毫秒毫秒 D170毫秒毫秒D D 4某数组有某数组有7个元素,依次为个元素,依次为158、234、369、478、552、697、748。若采用对分查找法在该数组中查找数据。若采用对分查找法在该
9、数组中查找数据748,需要查找的次数是需要查找的次数是 ()A1 B2C3 D4C C 5在有序单词序列:在有序单词序列:As、Book、Door、English、Floyd、Good、Hello、Sun中,用对分查找法找到单词中,用对分查找法找到单词“Good”所所需要的查找次数是需要的查找次数是()A1 B2C3 D4B B 6某某8位男生的肺活量数据放在数组元素位男生的肺活量数据放在数组元素a(l)到到a(8)中,其数中,其数据依次为据依次为“3205、3408、3471、3498、3621、3829、4233、4540”。使用对分查找,设定查找键。使用对分查找,设定查找键key,若第一
10、个被访,若第一个被访问到的数据是问到的数据是3498,小于,小于key值,则第二个被访问到的数据值,则第二个被访问到的数据是是 ()A3408 B3829C4233 D4540B B 7使用对分查找在已排序的数组使用对分查找在已排序的数组d(数组元素数组元素d(l)d(2)d(n)中查找中查找key的算法流程图如下。其中、框中的的算法流程图如下。其中、框中的内容分别是内容分别是 ()Ajm1 im1 Bjm1 im1Cjm1 im1 Djm 1 im1C C 8有两组数据:有两组数据:54、31、43、12、8、73、56、34、89、60、23、6787、83、75、70、63、59、55、
11、37、33、21、17、7下列有关查找方法描述不正确的是下列有关查找方法描述不正确的是 ()A可以直接使用顺序查找可以直接使用顺序查找 B可以直接使用对分查找可以直接使用对分查找C可以直接使用对分查找可以直接使用对分查找 D可以直接使用顺序查找可以直接使用顺序查找C C 9某查找算法的部分某查找算法的部分VB程序代码如下:程序代码如下:t Falsei 0Do While i a(i+1)Then k k 1 Else k 1(1)If k max Then k=max(2)Next i Text2.Text Str(max)End Suba(i-1)11.某学校把每个学生的姓名和家长联系电话
12、保存到计算机中,某学校把每个学生的姓名和家长联系电话保存到计算机中,以便遇到紧急情况时可以及时通知学生家长。每个学生的姓以便遇到紧急情况时可以及时通知学生家长。每个学生的姓名和家长联系电话已经保存在数组名和家长联系电话已经保存在数组xm和和phone(都为字符串类都为字符串类型型)中。现在要设计一个根据输入的学生姓名查询该学生家中。现在要设计一个根据输入的学生姓名查询该学生家长的联系电话的程序。程序运行时的界面如下图所示:长的联系电话的程序。程序运行时的界面如下图所示:完善程序:下列程序运行时,完善程序:下列程序运行时,在在Text1中输入学生姓名,单击中输入学生姓名,单击“查询家长电话查询家
13、长电话”按钮按钮Command1后,在标签后,在标签Label2中显示对应的学生家长电话,中显示对应的学生家长电话,若找不到则显示若找不到则显示“未找到该学未找到该学生生”。程序代码如下:。程序代码如下:Dim xm(1 To 1000)As StringDim phone(1 To 1000)As StringConst n As Integer 1000Private Sub Command1_Click()Dim x As String Dim find As Boolean Dim i As Integer x Text1.Text i 0 find False Do While(i
14、n)And find False If Then find True Loop If find True Then Label2.Caption “该学生家长联系电话为:该学生家长联系电话为:”phone(i)Else Label2.Caption “未找到该学生未找到该学生”End IfEnd Sub Private Sub Form_Load()学生姓名及家长电话数组赋初值语句,忽略学生姓名及家长电话数组赋初值语句,忽略End Sub请阅读代码并问答下列问题。请阅读代码并问答下列问题。(1)解决此问题的算法是解决此问题的算法是_。在程序和划线处填入适当的语句或表达式,将在程序和划线处填入适
展开阅读全文