对分查找算法及程序实现

《对分查找算法的程序实现》一、案例主题：浙江教育出版社《算法与程序设计》（选修），《对分查找算法的程序实现》二、背景材料：（一）教学内容分析：1.对分查找算法是《算法与程序设计》（选修）《5.4节查找算法的程序实现》中的内容，是结合流程图实现程序的课型。

本课内容是选修教材中对所学语句结构和代码理解的一个总结性应用，具有很强的实用性。

2.本课内容应用性较强，具有一定的难度，体现在对流程图理解和代码实现的过程中，但应用丰富，拓展性强，有很高的研究价值。

（二）学生分析：通过前面一个月算法的学习，学生已经逐步熟悉visual basic6.0的编程环境，掌握了顺序结构、分支结构、循环语句的用法，在前期教学中学生已经初步了解算法基础及算法表示，抽象思维相对较好。

对分查找的算法对学生来说比较抽象，学生能否清晰的想象比较关键，所以学习难度比较大，需要教师合理的引导帮助其来解决问题。

本课中学生可能会出现的情况：1.掌握三种基本结构，但是在综合思想算法上缺乏一定的掌握度。

解决策略：先介绍对分查找思想，然后再引入流程图和程序。

2.刚学过顺序查找，给他们的感觉是实现简单，容易思想上放松。

解决策略：要让学生从根本上区别顺序查找，以免混淆算法。

3.因为对分查找比较抽象，如果直接以代码的形式出现，学生会难以理解和接受。

解决策略：以生动形象的例子进行导入然后再进行教学，提高课堂效率。

三、教学设计：（一）教学设计思想：对分查找在整个选修教材中是一个重点和难点，本课以生动的实例做为课堂导入，强调教学重点，以动态的指针演示，让算法思路更具体化，并且逐个击破难点并得以程序实现，以半成品加工策略提高课堂效率。

本课主要通过“思维导图”的形式和任务驱动等教学方式引导学生自主探究探索、解决问题，通过小组同学的探讨实现对本课知识的掌握，教师通过合理的引导帮助学生理解，创设学生自主和互助学习的良好气氛，以达到理解对分查找算法和实现相应程序的目标。

查找算法——顺序、对分查找在到学习、工作和生活中我们经常需要在一系列数据中查找出是否有某个特定数据，如在图书馆按书目查找某本书，在运动会上查寻某运动员的比赛成绩，在网上搜索信息、使用QQ查找好友等，这时就会用到查找算法了。

•问题提出一、采用何种方法进行查找？1.顺序查找顺序查找是最容易想到，也是最容易实现的一种查找算法，方法是将要找的数据与数组中的每个数据从第一个开始逐一进行比较，直到找到或者全部找完。

（1）顺序查找算法流程图（3）编写程序代码。

Dim d(1 To 8) As Integer ‘有8个数据Private Sub Command6_Click() '顺序查找Dim i As Integer, key As Integerkey = Val( _______ ) '获取查找的数据For i = 1 To _______ '依次查找If __________ Then '找到了数据Label5.Caption = "在数组的第" + Str(i) + "个位置"Exit For ‘中断当前For循环End IfNextIf i =_______ ThenLabel5.Caption = "在数组中没有找到数据" + Str(key)End Sub如果数组中有n个元素，那么顺序查找的平均查找次数是（n+1）/2次，有没有效率更高的查找算法呢？对分查找2.对分查找算法：首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。

对分查找的前提条件数组中的数据是已经排序的。

对分查找算法流程图（3）编写程序代码。

Private Sub Command4_Click() '对分查找Dim i As Integer, j As Integer, key As Integer, m As Integer Dim nc,flag As Integerflag=0 ‘flag 用于标志是否找到 key = Val(Text2.Text) '输入查找的数据 i = 1 j = 18nc = 0 '查找次数nc Do While i <= j '对分查找 nc =—————— '查找次数增加1m = __________ ‘求中间下标，若有小数,只保留整数 If __________Then ‘找到了 Label6.Caption = "在数组的第" + Str(m) + "个位置，共查找了" + Str(___) + "次"flag=_____Exit do ‘强制退出循环’End IfIf key < d(m) Then '未找到，继续查找 j=__________ Elsei = __________ End IfLoopIf flag==____ thenLabel6.Caption = "在数组中没有找到数据" + Str(key) + "，共查找了" + Str(nc) + "次"EndifEnd Sub使用对分查找，每次都把规模缩小一半，效率比顺序查找要高，但在进行对分查找前，需要将它排好序。

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

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

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

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

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

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

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

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

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

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

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

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

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

专题5 顺序查找与对分查找算法一、基本思想查找是在大量的信息中寻找一个特定的信息元素，高考选考中查找算法包括顺序查找算法和对分查找算法。

1. 顺序查找顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。

若某个数据和给定值相等，则查找成功；如果所有的数据都比较过，没有一个数据和给定值相等，则查找不成功。

2. 对分查找对分查找的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找。

在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，则查找成功，或直到子表不存在，则查找不成功。

对分查找的条件是被查找的数据列必须是有序的。

二、顺序查找算法和枚举算法实现代码区分三、对分查找算法实现代码上面对分查找算法用一个块IF 语句实现，也可以用其他等价方法实现，以下举例两个：【注意】顺序查找没有找到key 时，循环结束后i>n (i=n+1)。

【注意】对分查找取中间位置m 的方法常见的还有：m=Int((i+j)/2)、m=Int((i+j+1)/2)、m=Fix((i+j)/2)、m =Fix((i + j) / 2 + 0.5)等，对分查找没有找到key 时，循环结束后i>j ( i=j+1) 。

四、二叉树的概念在计算机科学中，二叉树是每个节点最多有两个子树的树结构。

如下图：（b）完全二叉树1. 二叉树的每个结点至多只有二棵子树（不存在度大于2 的结点），二叉树的子树有左右之分，当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”；而最上面的结点叫做“根”。

二叉树的第i 层至多有2 ^（i-1）个结点，具有n个节点的完全二叉树的深度为log2 （N+1）。

2. 标准对分查找二叉树的建立假设先有10 个数据1、2、3、4、5、6、7、8、9、10①先取m 值为根节点，然后分成左右 2 堆数据放入左右2 个子树；②左右 2 堆依次求出m 值（2、8），m 值保留在原位，然后把 2 边数分别放入它的左右2 个子树（小的放左子树，大的放右子树）；③结点里还有2 个及以上数的，按照上面规则求m 值，m 值保留在原位，其他数放入它的左右 2 个子树（小的放左子树，大的放右子树）；3. 对分查找二叉树的一些性质①每个节点出发，往左走数字变小，往右走数字变大；②每个节点为每次计算的m 值；当时i 的值为左子树最左边的结点，如果左子树没有，i 就是本身m 值；j 值为右子树最右边的结点；如果右子树没有，j 就是本身m 值。

VB查找专题班级姓名知识点回顾：1、查找概念及意义：到一组有序或无序的数（如果数据是有规律的就可以不用数组）中找符合条件的数据。

意义：生活中查找应用广泛，所以研究查找算法很有必要。

2、顺序查找算法：从第一个元素开始，按顺序依次将数据与需查找的给定值比较，若某次发现数据相等，则退出查找，提示查找成功、数据所处位置或值等信息。

如所有数据查完，没找到，则查找不成功。

3、关于顺序查找需理解：※字符串也能查找与被查找，字符串相等的判断标准是从前往后每一个字符都相等※被查找的一组数据可以是无序的，当然有序也可以。

※实现要点是循环加选择，一般是for 加if语句，注意与枚举算法的区别。

※到N个数据中用顺序查找找一个数，最少查找次数1，最多查找次数n，平均查找次数（n+1)/25、对分查找算法：又名二分查找，高效，但前提是背查找的数据必须是有序的。

在有序的一组数据中，先将处于中间位置的数据与查找数据比较，若相等则提示成功；否则根据数组的有序性（升序或降序）判断要查找的数据在前半部分还是后半部分，然后缩小范围按以上方法继续查找，直到找到或找一遍发现数据不存在。

6、关于对分查找需理解：※到N个数据中用经典对分查找某数，最少查找次数1，最多查找次数int（log2n)+1，平均查找次数为：※被查找的一组数据必须是有序的，查找过程中注意其升序还是降序。

※查找次数不定，一般用do while 语句实现循环，请部分同学尝试将语句改为用for语句实现。

7、对分查找经典算法：（被查找数据以升序为例）巩固练习1、在数组22、54、7、61、33、9、15中查找数字9，采用从后往前顺序查找，需要查找（）A.2次B.6次C.1次D.7次2、数组 a(1 to 6)中保存的字符串依次为oil，car,boe,all,web,log，在数组中查找”boy”，执行知识点回顾4中顺序查找经典算法结果是（）A.没有找到B.在数组第1位置上找到数据boyC.在数组第3位置上找到数据boyD.在数组第6位置上找到数据boy3、小海同学用VB设计了一个模拟高考查分系统的软件。

对分查找算法及程序实现一、二分查找算法二分查找又称折半查找，是一种在有序数组中查找其中一特定元素的算法。

它的基本思想是：将数组的中间位置的数与要查找的数据比较，如果查找数据比中间位置的数小，则在数组的低半部分继续进行查找；如果查找数据比中间位置的数大，则在数组的高半部分继续查找；直到找到该数据或者查找范围为空为止。

二分查找的时间复杂度为O(log n)，由于其基本思想是二分法，所以称之为二分查找。

二、二分查找算法的实现1、二分查找的实现//二分查找// arr：被查找的有序数组// item：要查找的项int binary_search(int arr[], int size, int item)int low = 0;int high = size;int middle;while(low <= high)middle = (low + high)/2;return middle;else if (arr[middle] < item)low = middle + 1;elsehigh = middle - 1;}return -1; // 表示没有找到2、二分查找的递归实现//二分查找的递归实现// arr：被查找的有序数组// item：要查找的项// low ：数组的低位下标// high：数组的高位下标int binary_search_recursive(int arr[], int item, int low, int high)if (low > high)return -1; // 表示没有找到int middle = (low + high) / 2;return middle;else if (arr[middle] < item)return binary_search_recursive(arr, item, middle + 1, high);elsereturn binary_search_recursive(arr, item, low, middle - 1);三、二分查找算法程序实现#include <iostream>using namespace std;//二分查找// arr：被查找的有序数组// item：要查找的项int binary_search(int arr[], int size, int item)int low = 0;int high = size;。

一、顺序查找算法回顾1、顺序查找思路：1) 将被查的数存放到数组中（比如数组d ），待查的数据存放在某变量中（比如变量key ）2) 从数组第1个元素开始，逐个与要查找的数比较2、顺序查找过程 1）将被查的10个数存放到数组d ，将待查的数据存放到变量key 2）从数组第1个元素开始，逐个与变量key 比较，对于某个数组元素若d(i)=key，表示查找成功，输出该数组元素的下标 i ，并停止比较 若d(i)<>key ，则数组的下一个元素d(i+1)继续与key 比较...... 3）若找遍了所有元素，没有一个元素d(i)=key ，表示3、顺序查找方法归纳：笨拙4、上次课堂结尾的几个话题话题1：如何查英文词典（不可能采用顺序查找的！）话题2：如何在最短时间猜中1000元以内商品的价格？（每次猜中间价格！）话题3：如何在10个有序的数“98、88、82、78、70、67、65、56、49、28”中查找 49 这个数 如何在10个有序的数“28、49、56、65、67、70、78、82、88、98”中查找 99 这个数 有序数据采用“对分查找”方法（取中间的数进行比较）核心要点：区间（i,j)的中间数编号m=Int((i+j)/2)二、对分查找：前提是被查找的数据必须是有序的（递增/递减）1、对分查找的基本思想：每次将查找内容与有序数组内中间的那个数进行比较！第二章：算法实例—对分查找算法1(13)算法与程序设计1) 将被查找的数存放到数组中(必须有序！)，待查数据存放在某变量中（比如变量key）2) 区间（i,j）的起始为（1，n)，即初始值：i=1，j=n，(注意i<=j)3）每次将查找内容与有序数组内中间那个数比较。

区间（i,j)的中间数编号m=Int((i+j)/2)如果二者相等，则查找成功若二者不同，则根据数组的有序性可以确定在数组的前半部分还是后半部分继续进行查找。

4）直到找到，或者无法组成新的查找区间（即找不到）为止！2、对分查找过程示例1：在递增的数组d中寻找key=35这个数第3次末数3、对分查找过程示例2：在递减的数组d中寻找key=66这个数第3次第1次第2次第1次第2次第3次末数三、对分查找算法的程序实现！1、算法要点（从前面的练习中去感觉！）1、初值i=1,j=n2、循环条件：i<=j3、根据i,j计算m=Int((i+j)/2) 或者 m=Fix((i+j)/2)4、比较key与d(m)若key=d(m)查找成功，输出m若key<d(m)，则在上半区继续查找（增序为例），只要修改j=m-1即可若key>d(m)，则在下半区继续查找（增序为例），只要修改i=m+1即可思考：对分查找该用什么类型的循环呢？2、对分查找的程序理解!假设有10个数据已经按照升序存放在数组 D中，要查找的数据通过文本框Text1输入Dim d( 1 to 10) As Integerkey=Val(Text1.Text)i=1 : j=10 '查找区间初始化xb=0 '记忆查找成功时的下标nc=0 '统计查找次数Do While i<=j '为何不用For循环？nc=nc+1 'nc记录查找次数m=Fix((i+j)/2) '计算出中间位置，或m=Int((i+j)/2)If d(m)=key Then '查找成功立即终止循环xb=m'查找成功时变量xb记忆住数组下标Exit DoEnd IfIf key<d(m) Then'准备在上半区继续查找j=m-1Else'准备在下半区继续查找i=m+1End IfLoopIf xb<>0 Then '查找成功，输出下标xbPrint xbElse '查找不成功Print "没有找到"End If3、对分查找的程序流程图（略）四、对分查找算法巩固练习1、启动D：\下的“课堂练习.exe”，完成第27套课堂练习2、做完后将"批改27.批改"上传到班级FTP自己的文件夹内（ftp://10.7.3.100）中（比如变量key）不到的结论。

浙教版《算法与程序设计经典算法对分查找及VB实现知识点及课后练习对分查找是一种高效的搜索算法，常用于在有序数组中查找某一特定元素。

在浙教版《算法与程序设计》中，对分查找是一个重要的知识点。

下面将对分查找及VB实现的知识点及课后练习进行介绍。

知识点介绍：1、对分查找的基本思想：将有序数组分成两半，每次取中间值与目标值进行比较，根据比较结果确定继续在左半边还是右半边查找，直到找到目标值或查找范围为空。

2、对分查找的算法流程：（1）将数组按升序排列；（2）初始化两个指针，left指向数组的第一个元素，right指向数组的最后一个元素；（3）当left <= right时，执行以下步骤：a.计算中间位置mid=（left+right）/2；b.如果mid元素等于目标值，则返回mid；c.如果mid元素大于目标值，则在左半边继续查找；d.如果mid元素小于目标值，则在右半边继续查找。

3、VB实现：使用VB编写对分查找的代码，需要注意数组的索引是从0开始的，因此在计算中间位置时需要使用（left+right）/2，而不需要加1。

课后练习：1、对于以下数组：{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，使用对分查找查找元素13，输出查找过程。

2、对于以下数组：{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，使用对分查找查找元素2，输出查找过程。

3、对于以下数组：{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，使用对分查找查找元素-1，输出查找过程。

4、对于以下数组：{100, 200, 300, 400, 500}，使用对分查找查找元素300，输出查找过程。

在计算机科学中，冒泡排序是一种简单的排序算法。

这种算法通过重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。