专题05 顺序查找与对分查找算法（知识梳理）-巅峰冲刺2020年浙江省高考选考信息技术二轮专项提升

专题5 顺序查找与对分查找算法 一、基本思想 查找是在大量的信息中寻找一个特定的信息元素，高考选考中查找算法包括顺序查找算法和对分查找算法。 1. 顺序查找 顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。 若某个数据和给定值相等，则查找成功；如果所有的数据都比较过，没有一个数据和给定值相等，则查找不成功。 2. 对分查找 对分查找的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找。 在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，则查找成功，或直到子表不存在，则查找不成功。对分查找的条件是被查找的数据列必须是有序的。 二、顺序查找算法和枚举算法实现代码区分 顺序查找 枚举算法 思想方法 数据源从头到尾逐个比较 一一列举所有可能解并验证 核心代码 For（从数组的第一个元素到最后一个元素） If　当前元素＝关键词　the输出该位置 Next For（列举所有可能的解） If可能解是正确解then输出该解 Next 区分方法 ① For语句用于访问整个查找源的数据，一般是从开始位置到结束位置。 ② If语句用于判断当前访问的元素是不是等于关键词。 ③ 一旦某个位置的数据等于关键词，则记录该位置，并且查找任务结束，通常用语句Exit For退出循环。 ① For语句用于列举所有可能的解，即解的范围。 ② If语句是验证当前列举的可能解是否是正确解。 ③ 正确解可能有多个，因此找到一个正确解后，循环继续，直到所有可能的解都被检验过。 不管是枚举算法还是顺序查找，都可以写成For循环语句，区分的方法是要分析问题的本质：For 语句是为了一一列举所有可能的解还是从头到尾逐个访问数据源中的数据；If语句是检验可能解还是比较关键词。 三、对分查找算法实现代码 Key=text1.text ’输入关键词 i=1:j=n ’设置首次查找的范围 f=False ’ｆ标志是否已经找到关键词 Do whil