主讲教师：晁晓菲 西北农林科技大学·信息工程学院

Presentation on theme: "主讲教师：晁晓菲 西北农林科技大学·信息工程学院"— Presentation transcript:

1 主讲教师：晁晓菲 西北农林科技大学·信息工程学院
查找算法-二分查找法 主讲教师：晁晓菲 西北农林科技大学·信息工程学院 我所讲授的课程是《大学计算机基础》 ，这门课程是面向全校各专业大一学生开设的计算机入门课程。

2 热身 “购物街”视频 如果是你，你会怎么猜？

3 目标 掌握二分查找法的基本思想 能够应用二分查找法解决生活实例。

4 二分查找算法简介 1.二分查找算法是适用于有序序列的高效率的查找算法。 2. 它充分利用了元素间的次序关系，采用分治策略，不断 将待查找区域折半，直到找到待查找元素或者查找表为空 为止。二分查找法又叫折半查找法

5 例1. 假设给定有序表 （8,17,25,44,68,77,98,100,115,125），分别完成查找 K=77及K=78.
例题 例1. 假设给定有序表 （8,17,25,44,68,77,98,100,115,125），分别完成查找 K=77及K=78. L(Left) M (Middle) R (Right) 查找区域最左边位置 查找区域中间位置 查找区域最右边位置

6 例题 [ ] 找77 第一趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 68 1 2 3 4 5 6 7 8 9 10 L M R 68<77

7 例题 [ ] 找77 第一趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 1 2 3 4 5 6 7 8 9 10 L M R 第二趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 [ 100 ] 6 7 8 9 10 L M R 100>77

8 找到了！ 77=77 例题 找77 [ ] L M R [ ] L M R [ 77 ] L M R 8 17 25 44 68 77 98
第一趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 1 2 3 4 5 6 7 8 9 10 L M R 找到了！ 第二趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 [ ] 6 7 8 9 10 77=77 L M R 第三趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 [ 77 ] 6 7 L M R

9 77<78 例题 找78 [ ] L M R [ ] L M R [ ] L M R 8 17 25 44 68 77 98 100
第一趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 1 2 3 4 5 6 7 8 9 10 L M R 第二趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 [ ] 77<78 6 7 8 9 10 L M R 第三趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 [ ] 6 7 L M R

10 找不到！ 98>78 R<L：查找范围为空！ 例题 找78 [ ] L M R R L 8 17 25 44 68 77 98
第四趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 [ ] 7 L M R 98>78 第四趟 查找表 8 17 25 44 68 77 98 100 115 125 位置 1 2 3 4 5 6 7 9 10 找不到！ R<L：查找范围为空！ R L

11 二分查找算法基本思想 假设查找表中元素为升序 1. 将待查元素K与查找列表中间位置元素进行比较，若相等，则查找成功，查找结束。

12 二分查找法的应用-拓展1 1.输油管、输气管、水管等故障检测
案例1：输油管漏油点检测。中石化东黄输油管道发生石油泄漏事故，为了减少对环境的污染和中石化的损失，工人们需要尽快地找到漏油点，请大家互相讨论为这些工人师傅们支招吧。

13 二分查找法的应用-拓展1 1.输油管、输气管、水管等故障检测
案例1：输油管漏油点检测。中石化东黄输油管道发生石油泄漏事故，为了减少对环境的污染和中石化的损失，工人们需要尽快地找到漏油点，请大家互相讨论为这些工人师傅们支招吧。 L M L M R M R

14 二分查找法的应用-拓展1

15 二分查找法的应用-拓展2 2. 电路、电话线等故障检测
案例：杨凌区大寨镇到五泉镇之间的电话线路发生故障了，为了尽快恢复通讯，技术人员需要在这条长达10km（每隔50m一个电线杆）的电话线路中找到断点进行修复，请问这些技术人员如何能快速锁定断点所在大概位置。需要一个个电线杆来排查吗？

16 二分查找法的应用-拓展3 3. 用二分法求方程的近似解 定区间，找中点，中值计算两边看。 同号去，异号算，零点落在异号间。
周而复始怎么办?精确度上来判断。

17 总结 二分法的实质： 不断缩小查找范围，减少比较次数，提高查找效率。 是计算机科学中分治思想的完美体现

18 VS 总结 二分查找算法 顺序查找算法 待查找序列需有序 比较次数少 查找效率高 待查找序列无需有序 比较次数多 查找效率低
二分查找法是适用于有序列表的高效查找算法 根据应用场合选择正确的查找算法可以得到事半功倍的效果！

19 奖励 ! 20 课外活动 同学之间互玩猜数字游戏，体会并熟练掌握二分查找法的 规则
猜数字游戏：猜一个1-100之间的数，需要告诉猜数字的人所猜的数字是：“大了”、“小了”、还是“对了”。 1-100之间的数字最多需要7次即可猜中，1-1000之间的数字最多需要增加3次即可猜中。那么 ，采用二分查找法的话，最多需要几次猜中？ 奖励 ! 20

20