【二分查找】边界问题
【练习】http://111.229.45.229/
P1004 数字查找
P1005 等式配对
1004: 【二分】数字查找2
时间限制: 1 Sec 内存限制: 128 MB题目描述
输入n个数字，进行T次查询，每次输入关键字，查询第一个大于关键字的数字，若不存在则输出"NO"。
输入
第一行n和T，代表n个数字，T次查询
接下来一行n个数字
接下来T行表示每次查询的数字
输出
对于每次查询，输出结果
样例输入
5 3
2 3 1 4 7
6
1
7
样例输出
7
2
NO
【算法分析】
传统的对分查找其实并没有太多应用场合，许多题目背景中，我们无法直接判断出当前元素是不是答案。
不同于高考要求的传统对分，上题中我们无法直接得出查找的元素是否是我们想要的答案。以查找值5为例，我们只能判断当前的查找元素是否大于5，却不能知道是否前面还有大于5的，所以无法直接确定当前是不是第一个大于5的元素了。
当然，我们可以选择先查找5，查找结束后，在结束时的位置继续向右循环查找，这种方法可以很大程度上提高效率，但是对于某一些特殊数据仍然会耗费大量时间，这里需要用到对分查找边界了。
再举一个例子：
序列1、3、4、6、7、8、10，查找第一个大于5的元素。
观察这个序列，要查找第一个大于5的元素位置，这里用颜色标记出来：
1、3、4、6、7、8、10
红色的是符合（大于5）的，蓝色是不符合（<=5）的。由于我们希望找到第一个大于5的元素，此时，根据是否大于5，将区间分成了两部分，我们需要查找的是一个临界点，也就是两个区间的交接处，这是对分查找变体应用中最为常见的形式。
我们还是设置变量l，r，mid，key；
如果a[mid]小于key（不符合的），那么说明答案在右边，于是l=mid；
如果a[mid]大于key（符合的），那么说明答案在左边或者当前就是答案，于是r=mid；
最后一定会逼近答案
如下图所示，我们找的第一个大于5的数字，即紫色边界的右边第一个数字，为“6”。
【基本代码】
While L + 1 < R:
m= (L + R) >>1
Ifkey>a[m]: //分支1，落在右半区间
R= m
Else: //分支2，落在左半区间
L= m
Print(a[R])
我们分析这段二分查找的代码：
首先和传统二分的最大区别是只有两个分支（因为只有左右区间两种情况），这样一来，也就不存在中途跳出的情况了，必定是当L>=R时跳出。
那么，最终第一个大于5的位置是什么呢，l？r？还是mid？
如下图所示，这种模板下，L和R在跳出时，必定停留在这两个位置（可以多模拟几遍，会发现除非输入大于1等于10的数字，其它情况，在跳出时R的位置都刚好是答案）。
这是因为L和R的移动方式所导致的，由于L和R都只能移动到m，所以L和R都不可能越过紫色的“边界”，最后“隔海相望”，于是将循环边界设置为L+1<R。（小细节：如果输入的数字是一个大于等于10的数字怎么办？也就是说整个序列都不存在大于key的数字。具体解决办法可以写if语句特殊判定，或者将R的初始值改为n+1，在输出时特判）。
其实打法并不唯一，对于新手来说最后逼近答案时的临界情况是不好把握的，需要自己去推敲，这里共整理了4种模板。注意模板之间没有本质区别，一种模板可以无差别地替换成其它模板，其功能完全一样。
模板2：
While L <= R:
m= (L + R) >>1
Ifkey>a[m]: //分支1，落在右半区间
R= m-1
Else: //分支2，落在左半区间
L= m+1
Print(a[L])
此种模板下，L和R在跳出时的位置如下图所示，则对应的，答案变为a[L]。
模板3：
While L < R:
m= (L + R) >>1
Ifkey>a[m]: //分支1，落在右半区间
R= m-1
Else: //分支2，落在左半区间
L= m
Print(a[L])
此种模板下，L和R在跳出时的位置如下图所示，则对应的，答案变为a[L+1]或a[R+1]。
模板4：
While L < R:
m= (L + R + 1) >>1
Ifkey>a[m]: //分支1，落在右半区间
R= m
Else: //分支2，落在左半区间
L= m+1
Print(a[L])
此种模板下，L和R在跳出时的位置如下图所示，则对应的，答案变为a[L]或a[R]。
【小结】二分查找边界问题在编程中的应用更为广泛，但是由于其“模板”较多，导致初学者出现理解的混乱，事实上在抓住变化规律前，可以尝试先记住一种模板，之后渐渐理解其它模板。集中模板在本质上没有任何区别，互相之间可以完全替代。
二分查找的难点还是在于二分的建模和查找时的验证，这回在进阶篇中进行介绍（感觉又在挖坑，，，）。