从区间角度看“二分”-经典教学课件.pdf

不忘初心、牢记使命

——从区间角度看“二分”

路桥中学陈朝晖

最近网上对二分讨论热烈，昨天我们组李老师问到二分解题，原本自己压根就没准备写什么二分，今天想想
还是写点，凑凑热闹吧……。上周我们组阮老师在准备一节《二分解题指导》市复习课，记得当时我给了她8
个字：“不忘初心、牢记使命”，今天就拿它作标题吧。
查找算法中最常见的是线性探查（顺序查找），放到具体应用中有不同需求：数据查找时，数据可能存在（不
存在）；找到其中一个解即结束；也可能找到符合题意多个解，如何确保最优解……
不管怎样，二分查找本意就是查找，其算法代码描述并不复杂，但在具体应用中稍有不慎，易导致死循环。
接下来，让我们一起走进二分查找吧。

（1）二分的初心
“初心”——让我们不要忘记二分前提是数据有序，并由此引出二分查找效率高、适合大数据。
数据必须有序是二分使用的前提条件，如果脱离这个前提来谈二分，你不觉得很好笑吗！
二分是一种查找策略，二分其目的是为了加快查找速度，与之相应的还有三分。二分查找效率在大数据下方
能凸显出来。少量数据无需二分，如果你只有那么几个数据，有做二分的必要吗！

（2）二分的使命
“使命”——二分过程中始终要注意问题解在区间缩减、区间切割的过程中，要将有效区间留下来。
为加深对区间切割的理解，在下面纸带上我写了一组有序数据，请你每次对折并撕掉无效纸带，直到找出。
25

小结：n个节点，采用二分算法查找，最多查找次数是。

推论1：若有节点总个数为n的完全二叉树，则其树的高度k：

证明：若该完全二叉树总节点个数为n，树的高度为k，根据推k论=5有lo：g2n+1(n≥1)
，即：……（1）
−1−1
2对不等≤式（≤12）−两1侧(取≥对1数)，有：2≤<2
−1
所以，有，由l于ogk22为整数≤，log可2知<：log22

因此，有−1≤log2<，或者log2=k−1证毕。

（注：推论1=等同+(≥)=(+)(≥)

...................=.....(.......).+...(...≥...)...................................................
几点思考：在二分查找过程中，每次查找位置点key等同于二叉树的一个节点，

若将树中各节点查找过程绘制出来，则得到二分查找树。该二叉树特征如下。

1.二分查找对象是有序序列，查找结果为（=key、<key、>key），该二分查找树一定为一棵二叉树

2.由于每次查找均对应为找到的一个节点，所以树中所有内节点+叶节点和等同总节点数n。

3.左子树、右子树总节点数差值<=1，因此该二叉树是一棵平衡二叉树。

从区间看《二分查找》1
一、教学要点（探本溯源）：
在二分教学过程中，我担心部分老师对二分题型细节过度解读，而忽视了二分的本质。
应用背景1：判定问题解

在升序数组中查找的元素（找到问题解即结束）
a[0..Maxn-1],=key
012345678910
23567777131723

#★核心模板1★二分方式查找问题解（判定所有可能位置）
a=[2,3,5,6,7,7,7,7,13,17,23]
Maxn=11
i=0;j=Maxn-1
key=int(input())
whilei<=j:#循环条件：区间存在(循环结束:区间不存在i>j)（本意是找遍所有区间）
m=(i+j)//2#以m点为分界点,对区间进行切割
print("[%d,%d],%d"%(i,j,m))
ifkey==a[m]:break#找到问题解,结束二分
ifkey<a[m]:#区间切割,保留解所在区间[i..m-1]（m-1<j,区间缩小）
j=m-1
else:
i=m+1#区间切割,保留解所在区间[m+1..j]（m+1>i,区间缩小）

应用背景2：寻找最优解
在升序数组a[0..Maxn-1]中,查找>=key的下标最大元素（key=7,问题解有多个，找出最优解）
012345678910
23567777131723
分析：由于数据为升序，查找(>=key)下标最大元素，因此区间切割时保存的是右侧部分。
如果你取下整，考虑边界情况，；如果是问题解，则区间不改动，出现死循环。
m=(i+j)//2[x..x+1]m=xa(x)
因此，这里应该取上整。
m=(i+j+1)//2
说到这，我猜有个别老师对取上（下）整的使用不太明了。其实也简单，其本意就是变着花样缩减区间嘛！
结论：最优解留在右侧区间取上整m=(i+j+1)//2；最优解保留左侧区间取下整m=(i+j)//2。
#★核心模板2★查找问题最优解(也可能无解哦)
a=[2,3,5,6,7,7,7,7,13,17,23]
Maxn=11;i=0;j