10.对分查找 学案—2022届高考信息技术VB一轮选考复习专题

算法复习专题十 对分查找 【课前先导】 1.基本概念 对分查找的基本思想是在________的数据列（升序或降序）中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找，直到找到要查找的数据，则查找成功，或知道子表不存在，则查找不成功。 2.实现过程 【案例1】从12，25，37，42，65，72，88七个数中查找数37，每一次查找最中间的值，不能整除则取前面一个，查找到即跳出循环，请填写下表。 查找 次数 待查找的 下标范围 查找到的 元素下标 查找到的 元素值 比要查找的元素值 （更大/更小） 下一次查找应 （向左/向右） 1 [1,7] 4 42 更大 向左 2 3 【案例2】从12，25，37，42，65，72，88七个数中查找一个范围在[0,100]的数，查找到即跳出循环，如果所有数都查找完了但没有查找到也跳出循环，共会出现几种情况？ （1）如果把向左设置成L，把向右设置成R，最后输出的结果可能是______________________________二叉树： ______________________________。 （2）如果把向左设置成-1，把向右设置成+1，最后输出的结果可能是______________________________ ______________________________。 （3）规模为n个数的数据源，使用对分查找时，最多经过_________ _____次查找。5个数进行对分查找，平均次数为____________。 （4）最后的结果中，i、j、m的值之间有什么关系？ _______________________________________________________________________________________ 注：二叉树主要运用于基础的对分查找，考虑的是多种情况结果。 3.基本代码（升序序列中对分查找） 方法一： i = 1: j = n Do While i<=j m = Int((i + j) / 2) If