《第6课 二分查找》课件.pptx

第6课二分查找五年级下册

了解并掌握二分查找的基本思想。总结出二分查找与顺序查找的异同。熟练运用二分查找解决实际问题。学习目标

情境导入下课啦，小蓝和小红玩起了猜数游戏。小蓝从1到100之间随机选择了一个数字让小红猜，其中在小红每次猜出一个数字后，小蓝会给出相应的提示语。提示语1:“不是，请重猜!”或“恭喜你，猜对啦!”。提示语2:“不是，小了!”或“不是，大了!”或“恭喜你，猜对啦!”假如小蓝心里想的数字是59，小红应该如何设定猜数方案才能用最少的次数猜出59呢？

情境导入提示语一如果按照提示语1玩猜数游戏时，小红则需要把所有可能的数字一一列举出来，如：第一次：从1开始猜，“不是，请重猜!”；第二次：2，“不是，请重猜!”；…第五十八次：58，“不是，请重猜!”；第五十九次：59，“恭喜你，猜对啦!”。综上，小红总共需要猜59次才能猜到小蓝心里想的数字。怎样猜才会比较快呢？还有没有更好的查找方法呢？

情境导入这是简单的查找，即我们上节课所学的顺序查找方法。每次猜测都只能排除一个数字。如果小蓝想的是100，那么小红可能需要从1猜到100了。因此，这种方法是要靠“运气”来决定猜测的次数，即由所猜测的数字在序列范围中的位置所决定。

情境导入提示语二如果按照提示语2玩猜数游戏时，小红可以先猜数值范围内的中间值，再根据小蓝提示的大小关系，选定新的查找范围，这样每次把查找的范围变为了原来的一半左右，直到猜到数字。如：(1)根据数字范围是1～100，折中猜数字50，发现猜小了，因此要猜的数字在51和100之间；

情境导入根据数字范围是51～100，折中猜数字75，发现猜大了，因此要猜的数字在51和75之间02根据数字范围是51～75，折中猜数字63，发现猜大了，因此要猜的数字在51和63之间03根据数字范围是51～63，折中猜数字57，发现猜小了，因此要猜的数字在57和63之间04

情境导入根据数字范围是57～63，折中猜数字60，发现猜大了，因此要猜的数字在57和60之间05根据数字范围是57～60，折中猜数字58，发现猜小了，因此要猜的数字在58和60之间06根据数字范围是58～60，折中猜数字59，猜对啦。07综上，小红只要猜7次就可以猜到小蓝心里想的数字59。这显然比一个个去试猜的效率要高很多。

情境导入能够这样猜的原因是，要猜的数字在一个有序的数列中(1～100)，并且可以获得大小关系。这样，根据大小关系逐步缩小猜测范围，最终猜中具体的数字。

情境导入如果小蓝心里想的数字是77，你能在最快的时间猜出这个数吗？请把你们心中的猜数过程写下来。

01二分查找的基本思想

二分查找的基本思想在查找数据时，如果数据已经按照一定的顺序排列好了，也可以利用上述类似的方法，取大约居于查找范围中间位置的数与要查的数进行比较，然后根据大小调整查找范围，并最终找到该数据。这种查找数据的方法就是二分查找法。

二分查找的基本思想小贴士二分查找法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略。它是一种高效的查找方法，可以明显减少比较次数，提高查找效率。但是，二分查找法查找的前提条件是被查找的数据必须是有序的(可以从小到大排列，也可以从大到小排列)。

02二分查找的实例演示

二分查找的实例演示为了更直观地理解二分查找，我们通过一个实例来进行演示。假设有一个有序数组如下：[1，3，5，7，9，11，13，15，17，19]现在要查找的元素是11，我们采用二分查找算法进行搜索。元素135791113151719位置0123456789注：key＝11

二分查找的实例演示1.初始化起始位置low为0，结束位置high为数组长度9。2.计算中间位置mid=(low+high)//2=4。3.将待查找的元素11与中间位置的元素9进行比较，11大于9，所以在右半部分继续查找。1357911131517190123456789lowhighmidmid＝（low＋high）/2＝（0＋9）/2＝4判断key＞a【mid】更新low＝mid＋1＝5

二分查找的实例演示4.更新起始位置low为5，结束位置high不变。5.计算中间位置mid=(low+high)//2=7。6.将待查找的元素11与中间位置的元素15进行比较，11小于15，所以在左半部分继续查找。1357911131517190123456789lowhighmidmid＝（low＋high）/2＝（5＋9）/2＝7判断key＜a【mid】更新high＝mid-1＝6

二分查找的实例演示7.更新结束位置high为6，起始位置high不变。8.计算中间位置mid=(low+high)//2=5。9.待查找的元素11与中间位置的元素进行比较，查找