高中信息技术-3、查找算法课件-浙教版PPT课件.ppt

1 对分查找的基本思想对分查找的前提是数据已经有序 以递增为例 然后把待查找的数据与数组中间位置的数比较 如果比中间位置的数大 在数组的后半部分继续查找 否则在数组的前半部分查找 继续对分查找 直到找到待查找的数在数组中的位置或数组已无法对分 查找算法 1 下标 元素 数组d i I 1 J 16 M fix i j 2 8 第1次比较 Key d m 查找范围应该变成d 9 d 16 Key 52 我们用变量I和J记录所要查找范围的起始和终止位置 2 对分查找的基本过程 2 65 67 72 85 97 98 下标 元素 数组d I 8 1 J 16 M fix i j 2 12 第2次比较 Key d m 查找范围应该变成d 9 d 11 Key 52 我们用变量I和J记录所要查找范围的起始和终止位置 3 98 下标 元素 I 9 J 12 1 M fix i j 2 10 第3次比较 Key d m 找到了 Key 52 思考 如果key 33 能找吗 那么至少需要比较几次 4 5 3 当堂练习 利用对分查找 在某校报名参加学生会主席竞选的学号列表20080101 20080135 20080238 20080342 20080450 20080558 20080633 20080708 20080846 20080910中 查找学号为20080846学生的过程中 依次被访问到的学号是 A 20080450 20080708 20080846 B 20080450 20080708 20080910 20080846 C 20080558 20080708 20080846 D 20080558 20080708 20080910 20080846 6 4 对分查找的核心代码分析 Key Val Text1 Text i 1j numDoWhilei jIfd M KeyThenLabel1 Caption 在数组的 Str M 位置中 ExitSubEndIfIfd M KeyThenElseEndIfLoopLabel1 Caption 在数组中没有找到 Str Key m i j 2 i m 1 j m 1 Int i j 2 或fix i j 2 7 5 顺序查找 输入查找的元素值key 32 此时d i key 数组中的第3个位置 如果输入查找的元素值key 22 此时i等于5 超过数组中元素个数 找不到 从数组d的第1个元素d 1 开始 依次判断各元素的值是否与查找键key的值相等 1 过程 8 2 顺序查找的流程图 9 3 转化成程序 PrivateSubCommand2 Click 顺序查找Key Val Text2 Text Fori 1TonumIfd i KeyThenLabel2 Caption 在数组的 Str i 位置中 ExitForEndIfNextIfi num 1ThenLabel2 Caption 在数组中没有找到 Str Key EndIfEndSub 10 6 顺序与对分查找比较 11 例1 从中国上海到美国旧金山海底电缆共有15个接点 现在某接点发生故障 需及时修理 为了尽快断定故障发生点 一般至多需要检查接点的个数为个 点评 这种检查线路故障的方法 就是二分法的应用 二分法不仅可用于查找线路 水管 气管故障 还可以用于实验设计 资料查询 也是求解高次方程的常用方法 7 对分查找算法的实际应用 12 例2 在26枚崭新的金币中 混入了一枚外表与它们完全相同的假币 重量比真金的略低 现在只有一台天平 请问你最多称次就可以发现这枚假币 分析 本题可以通过二分法的思想来处理这种对称的问题 解 第一次各13枚称量 选出较轻一端的13枚 继续称 第二次两端各6枚 若平衡 则剩下一枚即为假币 否则选取出较轻的6枚继续称 第三次两端各3枚 选取出较轻的3枚继续称 第四次 两