对分查找

对分查找算法及程序实现一、设计思想对分查找是计算机科学中的一个基础算法。

对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。

本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。

为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。

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

（三）算法与问题解决例举 C 查找、排序与问题解决（2）通过实例，掌握使用数据查找算法设计程序解决问题的方法。

本课的《学科教学指导意见》内容：基本要求：1.初步掌握对分查找算法。

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

教材内容：第二章算法实例2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。

从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。

对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。

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

VB程序编写挑战木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。

当然，希望得到的小段越长越好。

现在用VB编写程序计算能够得到的小段木头的最大长度（木头长度的单位是cm，原木的长度都是正整数，要求切割得到的小段木头的长度也是正整数）。

功能如下：
文本框Text1里面输入正整数n，文本框Text2里输入k（1<=n<=10,1<=k<=100），n是原木的数量，k是需要得到的小段的数量，文本框Text3里依次输入n个数，每个数表示一根原木的长度，用keypress事件来完成每输入一个数，按回车，将其赋值给数组a(i)。

Label5中显示能够切割得到的小段的最大长度。

如果连1cm长的小段都切不出来，则输出“0”。

运行效果如第17题图
所示，其中文本框Text3
中依次输入3根原木的长
度为：232，124，456。

请
编写实现上述功能的VB
程序。

对分搜索法动态演示程序设计摘要：算法是程序设计的灵魂，也是语言课教学的难点，在教学法过程中，如果能加以计算机辅助教学，可以提高教学效果，同时编写这样的程序可大大增强学生的学习兴趣，提高学生的编程能力。

由于算法比较抽象，因此要理解和掌握其中的原理就比较困难。

通过对二分查找法的动态演示，让学生能更好地了解算法的来龙去脉，抓住算法的本质，从而激发了对程序设计这门课的学习兴趣。

关键词：对分查找法；动态演示；控件移动对于抽象的、难以理解的算法单纯地靠老师在讲台上讲和在黑板上画图，很难讲清楚，学生也似懂非懂。

如果制成动画，动态地，一步一步地演示，将深奥理论和逻辑推理的内容，直观、形象、清晰地展现在学生面前，使学生在头脑中产生一个深刻的印象，就会起到事半功倍的效果，使得本来索然无味的计算机编程课变得生动有趣、高效而又充满活力。

1.对分查找法的基本思想对分查找法又称折半查找，它的基本思路是：首先取有序数列的中间数据，与查找值c进行比较。

如果正好是要查找的数据，则查找成功，结束查找。

如果中间数据大于要查找的值c，则将小于中间数据的（即左半部分）一半对分，找出其中间值再与比较；如果中间数据小于要查找的值c，则将大于中间数据的（即右半部分）一半对分，再次进行比较。

根据比较结果，再对分相应的数据段。

如此对分比较下去，直找到要查找的数或当左端点l>r（右端点）为止。

其具体方法是：设置三个位置指针，即左端点指针l，中间位置指针m，右端点指针r，假设有序数列为a（1 to 12）左端点指针l=1，右端点指针r=12，中间位置指针m=int（（l+r）/2）1.1判断待查数x是否等于a（m）（中间数），如果是，则已找到，查找停止，否则继续下去；1.2判断待查数x是否小于a（m）（中间数），如果是，则必定落在左端点指针l和中间位置指针m-1的范围之内，下一步查找只需在这个范围内进行，左端点指针l指向不变，右端点指针r=m-1；1.3如果x大于a（m）（中间数），x必定落在右端点指针r和中间位置指针m+1的范围之内，下一步查找只需在这个范围内进行，右端点指针r指向不变，左端点指针l=m+1。

对分查找算法教案（5篇）第一篇：对分查找算法教案对分查找算法教案一、设计思想对分查找是计算机科学中的一个基础算法。

对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。

本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。

为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。

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

（三）算法与问题解决例举 C 查找、排序与问题解决（2）通过实例，掌握使用数据查找算法设计程序解决问题的方法。

本课的《学科教学指导意见》内容：基本要求：1.初步掌握对分查找算法。

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

教材内容：第二章算法实例 2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。

从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。

对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。

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

信号工考试：铁路信号工三1、填空题移频自动闭塞中继点的接受盒不控制通过信号机的显示，接受盒的UJ、LJ可用1个（）继电器代替。

正确答案：绿、黄2、填空题当地面发送的信息不变时，机车信号应（）不变。

答案（江南博哥）：保持3、填空题TYJL—II型计算机联锁系统通信正常时，表示各微机间通信状态的指示灯应不停地（）。

正确答案：闪烁4、单选JT-C系列机车信号记录器以插件形式插在机车信号主机机箱内，对机车信号的（）信息进行直接的采集。

A.输入输出B.感应C.点灯输出D.输入正确答案：A5、单选在调度集中区段的信号设备控制方式采用（）控制。

A.一级B.二级C.三级D.四级正确答案：B6、单选机车信号接收线圈必须安装在机车第一导轮的（）。

A、前方B、后方C、上方D、不限正确答案：A7、填空题第二种调车中途返回解锁是在调车车列（）折返信号机内方后开始解锁的。

正确答案：完全进入8、填空题JT-C型机车信号主机板动态监督电路U7芯片的型号是（）。

正确答案：74HC049、填空题JTl-CZ2000型机车信号通过（）控制，可以强行设置A机或B机为工作机或备机，为系统自动测试提供了基础。

正确答案：外部切换10、填空题信息移频滤波盘用于电气化区段，用来抑制牵引电流的（）及其谐波对移频自动闭塞设备的干扰。

正确答案：基波11、问答题《计规》对机车信号设备的绝缘标准是如何规定的？正确答案：安装于机车上的机车信号与列车超速防护设备的导电部分与机车车体的绝缘电阻（切断电源），用500V兆欧表测试时：蒸汽机车不小于0.2MΩ；电力、内燃机车不小于1MΩ；其配线及引入线的线间相互绝缘电阻不小于0.2M Ω。

机车信号与列车超速防护单项设备导电部分与其外壳间的绝缘电阻不小于25MΩ。

机车接收线圈与其外壳间的绝缘电阻不小于1MΩ。

连续式及接近连续式机车信号接收线圈的外壳上下两部分间的绝缘电阻不小于0.2MΩ。

12、单选TYJL-Ⅱ型计算机联锁系统，电务维修机显示屏上的提示栏，显示提示信息和（）。

第2轮复习对分查找算法顺序查找次数在1和n之间对分查找成功，最少查找1；对分查找无论是否找的到，最多查找[log2n]+1对分查找不成功，则最少查找[log2n]次比如 1 2 3 4 5 key=0.5(1) i=1 j=5 循环比较（i<=j）m=3 if比较（key<d(3)）i=1 j=2(2) i=1 j=2 循环比较（i<=j）m=1 if比较（key<d(1)）i=1 j=0(3) i=1 j=0 循环比较（i<=j）不成立，直接退出所以总共查找了2次，即[log2n]次1 2 3 4 5 6 7对分查找次数 3 2 3 1 3 2 31 2 3 4 5 6 7 8对分查找次数 3 2 3 1 3 2 3 4 平均查找次数=19/81 2 3 4 5 6 7 8 9对分查找次数 3 2 3 4 1 3 2 3 4 平均查找次数=25/9'对分查找原数组递减（1）i = 1: j = 6: nc = 0Do While i <= jnc = nc + 1·m = Int((i + j) / 2)If a(m) = Key ThenExit DoEnd IfIf Key>a(m) Thenj = m - 1Elsei = m + 1End If等价于Find=falsei = 1: j = 6: nc = 0Do While i <= j and not findnc = nc + 1m = Int((i + j) / 2)If a(m) = Key ThenFind=trueEnd IfIf Key>a(m) Thenj = m - 1Elsei = m + 1End IfIf find=true then print原数组递减以下代码能找到If Key>a(m) Thenj = m – 1Elsei = m + 1End If相关参考题目名卷精编2018A版 P11-18 P13-11 P31-11 P17-11P加试题训练4-11 此题没有简便方法P加试题训练10-12 此题没有简便方法变式题目1：Private Sub Command1_Click()Dim a(1 To 10) As Integera(1) = 8: a(2) = 15: a(3) = 26: a(4) = 30: a(5) = 37: a(6) = 50: a(7) = 55: a(8) = 68: a(9) = 83: a(10) = 106i = 1: j = 10Key = 15Text1.Text = ""Do While i < jm = (i + j + 1) \ 2 '注意取中值范围If Key = a(m) Then Exit DoIf Key < a(m) Then j = m - 1 Else i = m + 1Text1.Text = Str(a(m)) + Text1.Text '注意输出顺序答案 26 50LoopEnd Sub'i=1 j=10 m=6 a(m)=50'i=1 j=5 m=3 a(m)=26'i=1 j=2 m=2 a(2)=key 这一步很关键变式题目2：对分查找的递归函数表示方法Dim a(1 To 100) As IntegerDim k As IntegerFunction search(key As Integer, left As Integer, right As Integer) As Integer middle = (left + right) \ 2If left > right Thensearch = -1ElseIf a(middle) > key Thenk = k + 1: search = search(key, left, middle - 1)ElseIf a(middle) < key Thenk = k + 1: search = search(key, middle + 1, right)ElseIf a(middle) = key Thenk = k + 1: search = middle: Exit FunctionEnd IfEnd IfEnd FunctionPrivate Sub Command1_Click()k = 0a(1) = 2: a(2) = 4: a(3) = 6: a(4) = 8: a(5) = 10: a(6) = 13: a(7) = 15Print Str(search(6, 1, 7))'【6】表示查找数组元素值是6，【1】数组的开始下标为1，【7】数组的结束下标为7 'search函数的返回值是值为6的数组元素的下标Print k'值为6的数组元素查找次数End Sub。

2018年浙江省选考信息技术查找与排序强化习题⼀答案第⼆轮排序和查找算法综合1⾏政班：教学班：姓名：学号：根据课本上的排序算法和查找算法回答1-6题：1．【加试题】有⼀个数组，采⽤冒泡排序，第⼀遍排序后的结果为：4，10，5，32，6，7，9，17，24那么该数组的原始顺序不可能．．．的是（）A．10，5，32，6，7，9，17，24，4 B．10，5，32，6，7，9，4，17，24 C．10，5，32，4，6，7，9，17，24 D．4，10，5，32，17，9，24，6，72.【加试题】对下列数据序列进⾏冒泡升序排序，排序效率最低的序列（）A.31，29，24，20，15，10B.10，15，20，24，29，31C.29，10，31，15，20，24D.24，29，31，20，15，10 3．【加试题2】数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，⽤“对分查找”找到“69”的过程中，依次被访问到的数据是（）A．69 B．66、69 C．66、76、69 D．56、66、76、694.【加试题2】⽤对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34，55”中查找数字13,两种⽅法都能访问到的数字是（）A.3B.5C.8D.34 5.【加试题2】在有序单词序列“bike，cake，data，easy，feel，great，hive，mark,sweet”中，⽤对分查找算法找到“easy”过程中，依次被访问到的数据为（）A.feel, data, easyB.great, data, easyC.bike, cake, dada，easyD.feel,cake,data,easy6.【加试题2】下列有关查找的说法，正确的是（）A．进⾏对分查找时，被查找的数据必须已按升序排列B．进⾏对分查找时，如果查找的数据不存在，则⽆需输出结果C．在新华字典中查找某个汉字，最适合使⽤顺序查找D．对规模为n的数据进⾏顺序查找，平均查找次数是21 n7. 【加试题】实现某排序算法的部分VB程序如下：数组元素a(1)到a(5)的数据依次为“38，70，53，57，30”。

1.用二分（对半）查找表的元素的速度比用顺序法( )A．必然快 B. 必然慢 C. 相等 D. 不能确定2.具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B. 4C. 2.5D. 53．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。

A. 分块查找B. 顺序查找C. 折半查找D. 基于属性4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )A．（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D. (100，80，60，90，120，130，110)5. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LLB. LRC. RLD. RR7. 下面关于B和B+树的叙述中，不正确的是( )A. B树和B+树都是平衡的多叉树。

B. B树和B+树都可用于文件的索引结构。

C. B树和B+树都能有效地支持顺序检索。

D. B树和B+树都能有效地支持随机检索。

8. m阶B-树是一棵( )A. m叉排序树B. m叉平衡排序树C. m-1叉平衡排序树D. m+1叉平衡排序树9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。

A．1 B. 2 C. 3 D. 410.下面关于哈希(Hash，杂凑)查找的说法正确的是( )A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可11. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需(（1）)个链表。

第8章 查找 自测卷答案一、填空题（每空1分，共10分）1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)二、单项选择题（每小题1分，共27分）（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

信号工考试：铁路信号工题库知识点三1、问答题什么是JTl型通用式机车信号简化的功能测试？适用于什么情况？正确答案：因JTl型数字化机车信号采用数字信号处理方式，不同制式、不同载频的信号通过同一处理通道处理，（江南博哥）它还有完善的软硬件自检功能，日常出入库检查时只需发送某些信号检查显示机构每个灯位都能点亮即可，这就是机车信号简化的功能测试。

简化的功能测试适用于日常的机车出入库检查。

2、填空题、UM71轨道电路的使用条件确定以后，应根据轨道电路的轨长、频率、电缆实际长度、（）类型，查《维规》“附录六：UM71电器绝缘轨道电路调整表”进行调整。

正确答案：轨道绝缘3、单选机车信号主机与配线盒间的连接电缆超过（）时需要屏蔽电缆。

A、1mB、1.5mC、2mD、2.5m正确答案：A4、填空题整机试验摩擦连接器摩擦电流应调整到额定电流2A的1.3倍，（）不大于0.3A（仅允许上偏差）。

正确答案：定，反位5、填空题信号电路图中时间继电器符号中的数字代表（）。

正确答案：延时时间6、问答题怎样处理TYJL-Ⅱ型计算机联锁系统采集故障？正确答案：采集故障首先要分清是机柜内故障，还是机柜外断线。

1.采集板面板灯是否亮灯，若不亮可用万用表电压挡测发光二极管两端有否电压，有电压而灯不亮，则发光二极管损坏，更换采集板即可。

2.采集板上的发光二极管完好而面板灯不亮，则说明故障在机外，可能是断电器接点接触不良.采集线断线.接口插座松动等。

若只上个别对象采集不到，可怀疑是采集板故障。

3.检查采集电路时，可借助采集地测量各采集点是否有12V正点，采集地在机柜零层端子板的1号端子上。

7、单选TDCS机柜采样控制板将采集到的信息通过串口（）发送到通信机的多串口上。

12C.并口1D.并口2 正确答案：A8、填空题ZP.Y2—18型移频自动闭塞区段发送盘应保证轨面送端电压不小于5---8V，最低不小于（）V。

正确答案：3.39、问答题道岔表示继电器抖动是什么原因？正确答案：道岔表示继电器抖动的原因是并联在道岔表示继电器线圈的电容故障（开路）或电容联线开路。

二分查找的概念二分查找是一种在有序数组中查找目标元素的算法，它的基本思想是每次将数组分成两半，比较中间元素和目标元素，如果相等则返回中间元素的索引，如果不相等则根据大小关系舍弃一半数组，继续在剩下的一半数组中重复这个过程，直到找到目标元素或者数组为空为止。

二分查找的时间复杂度是O(logn)，空间复杂度是O(1)，它是一种高效且简洁的查找算法。

二分查找的实现二分查找可以用递归或者迭代的方式实现，下面我们分别介绍两种实现方法。

递归实现递归实现的核心是定义一个辅助函数，该函数接受四个参数：数组、目标元素、左边界和右边界，表示在数组的左右边界之间查找目标元素。

该函数的逻辑如下：如果左边界大于右边界，说明数组为空，返回-1表示未找到目标元素。

计算中间位置mid = (left + right) / 2，比较数组中的mid位置的元素和目标元素。

如果相等，返回mid表示找到目标元素。

如果不相等，根据大小关系判断目标元素在左半部分还是右半部分，然后递归调用辅助函数，在相应的半部分继续查找。

返回递归调用的结果。

用Python语言实现递归版本的二分查找如下：def binary_search_recursive(arr, target):# 定义一个辅助函数def helper(left, right):# 如果左边界大于右边界，说明数组为空，返回-1if left > right:return-1# 计算中间位置mid = (left + right) //2# 比较中间元素和目标元素if arr[mid] == target:# 如果相等，返回midreturn midelif arr[mid] > target:# 如果中间元素大于目标元素，说明目标元素在左半部分，递归调用辅助函数，在左半部分继续查找return helper(left, mid -1)else:# 如果中间元素小于目标元素，说明目标元素在右半部分，递归调用辅助函数，在右半部分继续查找return helper(mid +1, right)# 调用辅助函数，在整个数组范围内查找return helper(0, len(arr) -1)迭代实现迭代实现的核心是使用一个循环，每次循环都更新左右边界的值，直到找到目标元素或者左右边界交叉为止。