对分查找算法及程序实现

一、设计思想

对分查找是计算机科学中的一个基础算法。对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。

二、教材分析

本课的课程标准内容：

（一）计算机解决问题的基本过程（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。

（三）算法与问题解决例举 C 查找、排序与问题解决

（2）通过实例，掌握使用数据查找算法设计程序解决问题的方法。 本课的《学科教学指导意见》内容：

基本要求：1.初步掌握对分查找算法。

2.初步掌握对分查找算法的程序实现。

教材内容：第二章 算法实例 2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算

法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。

从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。

三、学情分析

学生应该已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分解动作、比较迁移等学习策略。

四、教学目标

知识与技能：理解对分查找的概念和特点，通过分步解析获取对分查找的解题结构，初步掌握对分查找算法的程序实现。

过程与方法：通过分析多种不同的可能情况，逐步归纳对分查找的基本思想和方法，确定解题步骤。

情感态度与价值观：通过实践体验科学解题的重要性，增强效率意识和全局观念，感受对分查找算法的魅力，养成始终坚持、不断积累才能获得成功的意志品质。

五、重点难点

教学重点和难点：分解并理解对分查找的过程。

六、教学策略与手段

1、教学线索：游戏引领---提出对分查找原理--- 解析对分查找的算法特征---实践解决问题。

2、学习线索：分解问题---归纳问题---实践提升，在三个阶段的不断推进中明确对分查找算法，总结规律。

七、教学过程

1、新课导入

（1）热身：游戏（2分钟）

教师展示一件特色物品，让一个学生来猜这个物品的价格，其他学生只需要根据这个学生猜出的价格提示“高了”或是“低了”，如果学生能在五次内猜对这个物品的价格，就把这件物品“赠送”给他……。

（2）讨论：你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？你从这个游戏当中得到什么启示？(3分钟)

（3）教师引导：这个世界不是缺少问题，而是缺少发现，其实在这个游戏的背后，含有一个非常经典的算法。引出对分查找的的概念。

2、新课：

教学步骤一：分析对分查找的原理和思想。（3分钟）

（1）对分查找是效率很高的查找方法，但被查找的数据必须是有序的。

（2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。

（3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 教学步骤二：分解对分查找算法（5分钟）

假设：用一个数组d（1 to 10）来存放升序的元素序列，用i表示查找范围的起始位置的下标，j表示终止位置的下标,mid表示中间位置元素的下标。

（1） 第一种情况：要找的值在后半部分；

以查找键KEY=48为例分析

d(1) d(2)

d(3)

d(4)

d(5)

d(6) mi

第一次比较：

范围d(1)～d(10),mid= (1+10)\2, d(mid)<Key 所以可以确定接下来要找的范围是后半部分。 比较后i=mid+1

第二次比较：

范围d(6)～d(10),mid= (6+10)\2,d(mid)<Key 所以可以确定接下来要找的范围是后半部分。 比较后：i=mid+1

第三次比较：

d(9)

范围d(9)～d(10)，

mid= (9+10)\2,d(mid)=Key ，找到了。

d(10)

i mij

d(6) d(7) d(8) d(9) d(10)

j

i

mid

思考：如果要找的是52? i,j,mid分别是多少？

这也说明当i=j的时候是查找的最后可能次数，这也是终止查找的一个关键条件。

教学步骤三：继续分解对分查找算法中包含的其他情况。

画一画：请仿照上面的画法,分别画出key=17和key=20的查找示意图。 （2） 第二种情况：要找的值在前半部分； 以查找键KEY=17为例分析：

d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8)

mii

d(1) d(2) d(3) d(4)

j mi

i d

(3) d(4)

i mij

结果分析：

第一次比较后：j=mid-1第二次比较后：i=mid+1第三次比较后：找到了

（3）第三种情况：要找的值找不到；以查找键KEY=20为例分析： d(1) d(2)

d(3)

d(4)

d(5)

d(6)

d(7)

d(8) d(9)

d(10j mii d(1)

d(2) d(3) d(4) j d(4) i,j,mid

i mi

i mid j

结果分析：

第一次比较后：j=mid-1第二次比较后：i=mid+1

第三次比较后：i=mid+1第四次比较：i=j 但是d(mid)≠key,所以找不到。 教学步骤四：对各种情况进行归纳总结。

（1）Key与d(mid)的大小比较影响i,j的取值的规律：

i的取值规律：if d(mid)<key then i=mid+1

j的取值规律：if d(mid)>key then j=mid-1

用分支结构实现。

(2)继续进行重复查找的条件： i≤j，用循环结构实现。

教学步骤五：构建对分查找的流程图

教学步骤六：对分查找算法的初步程序实现。

教师事先设计好Vb窗体，学生只需要在相应的程序体输入代表算法思想的关键语句。

附主要程序体：

Private Sub Command2_Click()

Dim key As Integer, mid As Integer, i As Integer, j As Integer key = Val(Text1.Text)

i = 1: j = 10

Do While i <= j

mid = (i + j) \ 2

If d(mid) = key Then

Text2.Text = "找到了，是第" & mid & "个"

Exit Sub

End If

If d(mid) < key Then

i = mid + 1

Else

j = mid - 1

End If

Loop

Text2.Text = "找不到"

End Sub

程序说明：1、获得要查找的数据key的值 key = Val(Text1.Text)

2、i,j赋初值。 i = 1: j = 10

3、求mid的值。mid = (i + j) \ 2

4、分三种情况，（1）如果key=d(mid),则如果 d(mid) = key 那么 Text2.Text = "找到了，在第" + Str(mid) + "个"。

（2）如果key>d(mid),那么i=mid+1 否则 j=mid+1

5、重复上述的3,4步，直到i超出j(或者理解为i<=j不成立，所以不能用for next,而要用do while语句）

6、如果有找到key,那执行第4步（1）步后应该输出找到的位置后退出程序，如果不退出，说明key没有找到，所以在相应位置要输出“找不到”。

教学步骤七：评价。

评价学生的程序实现情况，并讨论或实践问题：如果是降序序列，该怎么样改动程序？如果序列元素不是10个，而是100个或更多呢？

教学步骤八：总结提升。

（1）由于对分查找过程中的每次比较都能使得搜索空间减半，对分查找将不会使用超过log2n次比较来找到目标值。

（2）提升对分查找算法的实际意义：同学们可能还没有意识到二分查找是多么高效，那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字，二分查找可以让你不超过21次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序，那么你可以在35步以内找到任何人。

八、作业：

1、以下的三组元素序列能采用对分查找法来查找吗？

(1) 19，33，35，53，56，67，78，99

(2)53，35，67，78，56，99，33，19

(3)99，67，56，45，33，10，9，1，0，-9

2、设计一个能用对分查找算法思想解决的实际问题。

【参考资料】 网络文章类

/

 

第二篇：分块查找算法

分块查找算法

分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。

1、分块查找表存储结构

分块查找表由"分块有序"的线性表和索引表组成。

（1）"分块有序"的线性表

表R[1..n]均分为b块，前b-1块中结点个数为

（2）索引表

抽取各块中的最大关键字及其起始位置构成一个索引表ID[l....b]，即：

ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

【例】下图就是满足上述要求的存储结构，其中R只有18个结点，被分成3块，每块中有6个结点，第一块中最大关键字22小于第二块中最小关键字24，第二块中最大关键字48小于第三块中最小关键字49。

，第b块的结点数小于等于s；每一块中的关 键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。

2、分块查找的基本思想

分块查找的基本思想是：

（1）首先查找索引表

索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

（2）然后在已确定的块中进行顺序查找

由于块内无序，只能用顺序查找。

3、分块查找示例

【例】对于上例的存储结构：

（1）查找关键字等于给定值K=24的结点

因为索引表小，不妨用顺序查找方法查找索引表。即首先将K依次和索引表中各关键字比较，直到找到第1个关键宇大小等于K的结点，由于K<48，所以关键字为24的结点若存在的话，则必定在第二块中；然后，由ID[2].addr找到第二块的起始地址7，从该地址开始在R[7..12]中进行顺序查找，直到R[11].key=K为止。

（2）查找关键字等于给定值K=30的结点

先确定第二块，然后在该块中查找。因该块中查找不成功，故说明表中不存在关键字为30的结点。