对分查找算法复习课件

课题 对分查找算法 复习 对分查找算法 一 生活中的对分查找 淘宝网上热卖的终极飞翼擎天柱 猜价格游戏 游戏规则如下 1 在给出这个玩具的价格是在100到200之间的整数 2 竞猜价格时 先猜100 200之间的中间价格 如果太小了 就猜150 200之间的中间价格 依此类推 直到猜对为止 我来试试 我愿意一试 150 太小 175 太大 163 太小 169 太小 172 太大 170 恭喜您猜对了 二 对分思想 验证奇迹 1 对分查找的基本思想 1 前提 被查找的数据序列必须是有序的 2 基本思想 在有序的数据序列中 一般放在数组中 首先把查找的数据与数组中间位置的元素进行比较 若相等 则查找成功并退出查找 否则 根据数组元素的有序性 确定数据应在数组的前半部分还是在后半部分查找 在确定了新的查找范围后 重复进行以上比较 直到找到或未找到为止 验证奇迹 对分查找实际数据演示动画 3 算法的基本框架 说明 要查找的数为key 待查找的数存在数组d中 i为查找范围的起点 j为查找范围的终点 m为范围 i j 的中间位置 find为查找成功与否的标记 find为true代表查找成功 find为false代表查找失败 i 1j 16find false 查找的结果 若为true表示找到 若为false表示未找到dowhile id m 则重新调整查找范围i m 1 i j 若key d m 则重新调整查找范围j m 1 i j Loop若find为真 表示查找成功 并输出找到的位置m 若find为假 表示查找失败 4 对分查找算法的流程图实现 请将 补充完整 三 琢玉成形 化玉为器 转化为程序代码 通过上述16个数据中查找key过程 程序代码如下 i 1 j 16 find falseDowhile id m then 表示待查数据比中间位置上的数大时i m 1 重新调整查找范围的起始位置i m 1else 表示待查数据比中间位置上的数小时j m 1 重新调整查找范围的终点位置j m 1endifLoopIffindthen 判断查找的结果 若为true表示找到 若为false表示未找到label1 caption 找到 该数在数组中的位置为 Str m elselabel1 caption 未找到 该数在数组中不存在 endif 通过上述16个数据中查找key的过程 推广至n个数据中查找 i 1 j n find falseDowhile id m theni m 1elsej m 1endifLoopIffindthenlabel1 caption 找到 该数在数组中的位置为 Str m elselabel1 caption 未找到 该数在数组中不存在 endif 打开 上机实践 文件夹中的 对分查找 vpb 文件 将窗体中 对分查找 按钮事件过程 Command3 Click 中的代码补充完整 注 带红色 处 并调试程序使之运行成功 四 体验之旅 感受程序魅力 1 对分查找算法中被查找数据是降序的情况程序该如何修改 i 1 j n find falseDowhileid m then else endifLoopIffindthenlabel1 caption 找到 该数在数组中的位置为 Str m elselabel1 caption 未找到 该数在数组中不存在 endif 五 思想升华 化茧成蝶 2 对分算法几个注意问题 1 对分查找的前提 被查找数据必须是有序的 2 新的查找范围的确定 i m 1或j m 1 3 查找结束的判断条件 找到数据 find true 或i j 3 对分查找算法的最多查找次数 4 对分查找算法的实际意义 对分查找的高效性 1 一个包含一百万个人名的电话簿中找一个名字 对分查找可以让你不超过20次就能找到指定的名字 2 将全国13亿人按身份证号排列后 你可在31次比较后找到这个人的信息 若用顺序查找还有这个效率吗 假设每次对分最坏情况 直到最后一次才找到就会有2 k n 2得到k long2n 1 二分法每次都会把范围缩小一半 因为最后剩一个元素时 也要执行查找过程 所以 1 六 夯实基础 查漏补缺 某8位男生的肺活量数据放在数组元素a 1 到a 8 中 其数据依次为 3205 3408 3471 3498 3621 3829 4233 4540 使用对分查找 设定查找键key 若第一个被访问到的数据是3498 小于key值 则第二个被访问到的数据是 A 3408B 3829C 4233D 4540 2 某数组有7个元素 依次为200 202 204 205 210 215 218 若采用对分查找在该数组中查找数据200 需要查找的次数是 若采用顺序查找数据200 需要查找的次数是 这能说明顺序查找算法比对分查找算法效率高吗 A 1B 2C 3D 4 3 我们育才高中在校生大约有1500人 学号有序排列 若现在利用对分查找来查找你的学号 最多需要查找 次就能找到你自己 A 10B 11C 12D 13 4 还原高考 医保卡余额查询 小朱设计了某单位医保卡余额查询系统 输入卡号 可以查出该卡号对应的余额 该单位共有n n 500 名职工 所有职工的医保卡号码和相应的余额等数据存放在数据库文件 company accdb 的worker表中 程序界面如图所示 左边列表框List1中显示的是全部职工的卡号 姓名和余额 在文本框Text1中输入职工的卡号 单击 查询余额 按钮 Command1 后 如果找到此卡号 则在标签Label5中显示 此人的卡号 姓名和余额 如果未找到则显示 找不到此卡号 请重新输入 程序实现代码如下 Dimkh 1To500 AsLong kh用于存储卡号Dimnam 1To500 AsString nam用于存储职工姓名Dimye 1To500 AsSingle ye用于存储医保卡余额Dimn i jAsIntegerPrivateSubForm Load 数据库链接与打开代码略 从数据库中读取每条记录的卡号 姓名 余额分别存于kh nam ye数组中DoWhilenotrs EOFn n 1kh n rs Fields 卡号 nam n rs Fields 姓名 ye n rs Fields 余额 rs movenextLoop 将从数据库中读取出来的数据按余额升序排序Fori 1Ton 1Forj nToi 1Step 1Ifkh j kh j 1 Thent kh j kh j kh j 1 kh j 1 tk nam j nam j nam j 1 nam j 1 kp ye j ye j ye j 1 ye j 1 pEndIfNextjNextIList1 AddItem 本单位共有 Str n 名职工 Fori 1TonList1 AddItemStr kh i nam i Str ye i Nexti 实现对卡号的查询 并显示所找到的卡号的医保卡余额PrivateSubCommand1 Click Dimx mAsIntegerDimfAsBooleanx Val Text1 Text i 1j nf FalseDoWhile i j andf m i j 2 Ifx kh m Then ElseIfx kh m Then Elsei m 1EndIfLoopIff