二分思想真的是无所不在，即使在中文系的专业课中我们也能见到这个词。在语言学概论中我们提到，一个音位可以由一组区别特征确定下来，这些区别特征总是以只具有“是/否”、“有/无”等两种对立属性的“二元偶分组”形式存在，因为这样可以最方便最快捷地确定出一个元素。这有点像猜数字一样，我想一个数字后让你来猜，我告诉你你的猜测是大了还是小了。只是在这里，回馈的信息不再是大小，而是“辅音/元音”、“口音/鼻音”、“浊音/清音”、“送气/不送气”等形式逐层细分。这让人联想到5张卡片猜年龄的老把戏，一系列火星的称球问题，基于比较的排序算法的复杂度下界，或者经典的20q在线游戏。
    一个有趣的事实是，相当多的人都错误地理解了“二分”这个词，但他们在生活中却拥有很强的二分意识。我们语言学概论的老师（这里就不说是谁了）在讲解二分时举了一个甚为荒谬的例子：如果你要在房间里找一根针，那么你可以把房间划分为两半，如果这一半找不到的话说明针一定在房间另一半，此时再把那一半分成两部分，不断分分分分分最后总能找到针的位置。这是这位老师无数荒唐的例子中的冰山一角，因为这个“二分”与搜索别无二致。这个“二分”的判断环节并不是即刻返回的，而且最关键的是它并不具有规模减半的功能，或者说一旦返回“真”后我们并不会再接着二分下去。如果让我来举例子的话，同样是拿找东西打比方，在合唱队中找出跑调了的人是一个绝佳的例子，因为在合唱中我们能轻易分辨出一个不和谐的声音（虽然无法准确判断这个声音是从哪儿传来的），不断叫当前的人的其中一半来合唱便可渐渐判断出那个人的位置。但讽刺的是，这老师在举这个错误例子的同时，竟然在不自觉地用二分法来调整课件的字号。他发现这一页ppt的字号太小了，我们可能看不清，于是希望让字号尽可能的大但又不致于大到显示不下。他开始尝试40号，发现字已经超出屏幕了；然后把字体改成20号，又觉得还能再大一些；进而又改到28号（工具栏上的字号调整以4为步长），最后确定到了24号字。

    如果真的叫一个课讲的好的老师来说二分，课程可以变得相当有意思。每次回我们高中时我都讲了很多次课，我最喜欢聊到的话题之一就是二分。从猜数游戏引入二分查询有序队列中的指定元素，然后提出一些标准的有序队列二分搜索的实际应用，比如解方程x^x=100一类的问题。紧接着提出二分的各种有趣的变形，例如如何在有序整数序列中查询A_i=i的元素。提出这些问题的目的就在于告诉大家，二分的思想不仅仅是用在猜数游戏一类的情况下。二分判断并不只限于“比目标值大/比目标值小”，只要能判断出目标值在哪边都行，例如在这里，A_i<i表明目标元素一定还在右边，A_i>i则表明目标元素在左边。

 i  =    1   2   3   4   5   6   7   8   9   10
A_i = -100 -20  -3   0   2   6  13  14  27  298

    另一个经典的变形则是分段有序队列中的二分查询。假如有这么一个数列，它可以分为前后两个部分，两段各是一个递增数列，并且后一段的最大值比前一段的最小值还要小。比如说，数列12, 15, 19, 3, 6, 7, 9, 10就是这样一个数列。这相当于是一个有序数列循环移动之后的结果。如何在这个数列中查询指定的元素呢？事实上，这种“有序序列”虽然经过了变形，但丝毫不影响二分法的应用，因为我们依旧能判断出目标值在当前值的哪一边（这是很显然的，我不多解释了），这就已经足够了。
    不结合实际应用的话，这些似乎没有实用价值的理论会变得乏味。其实，只要仔细思考，生活中对应的现象总是有的。我的秘方就是，想不出例子就想MM，爱情的复杂性保证其蕴含了各种千奇百怪的数学模型。一想到爱情，分段有序队列就能用上了。不妨为恋爱前后的“愉悦程度”建一个简单的模型：在恋爱之前，你会为找不到MM而越来越难过；一旦开始热恋愉悦值瞬间达到极大；之后热情会慢慢减小，但愉悦值始终比恋爱前要大。好啦，如果你想出一道题的话，问题背景已经是现成的了，不妨再定义一个符合这个模型的且不能直接解出来的分段函数，编几句形如“科学家发现恋爱前的愉悦值以a减某某某的速度递减，恋爱后则变为曲线a加某某某”的话，然后就来看看有多少人还能想到二分法吧。一般说来，好的题目背景起到了一个很强的干扰作用：题目背景越顺理成章，问题描述越是简单，看清问题背后隐藏的算法障碍就越大。另外，如果你给的函数巧妙到还需要大家先证明它的单调及有界，那这题目就真的绝了。

    要比谁的题目更绝，那绝对比不过USACO。USACO月赛中的二分题是真牛B了。我对二分的热情是相当的高。为高一高二的几个人备战省选时，我出了好几套模拟题，前面四套题每套都有一道来自USACO月赛的二分题。这个二分题是越来越诡异，以至于大家越来越难看出这套题里面哪道要用二分了。
    第一套题里的二分题是一个简单题：把一个长为N的数列划分为M段，要求每段数之和的最大值最小。例如，把100 400 300 100 500 101 400分割成5块，则100 400 | 300 100 | 500 | 101 | 400是最优方案之一，最大值500已经不能再小了，这个题一看就知道是二分后贪心判断，“最大值最小”之类的关键词几乎成了二分题的信号灯。像什么最小权值最大的完全匹配、瓶颈生成树问题（求最大边最小的生成树：二分后判断连通）、寻找权值波动最小的路径（找一条从A到B的路径使得所经过的边的最大权值和最小权值相差最小：枚举下界二分上界判断连通，滑动窗口更好），都是二分的经典问题。
    第二套题中的二分也是“最大值最小”类的问题，只是要更复杂一些：在带权无向图中，选择一些边使得A、B两点连通，要求费用最小。费用是这样算的：先从图中选出K条边（K值是给定的），免费；然后从图中选择其它你需要的边，费用为这些边的最大权值。这个题里，选边过程的先后顺序有一个很强的误导作用。事实上，正确的算法应该是先二分这个最大权值，再来判断把K条免费边的机会用上能不能把A、B连通，换句话说就是要想把A、B连通还差的边数超没超过K。当时做这个题时，不少人二分法是想到了，但却怎么也想不到该如何计算最少还需要多少条边才能连通A、B两点。其实方法很简单，把不超过当前二分出来的那个“最大权值”的所有边权值设为0，其它边的权值设为1，然后找一下最短路就可以了。
    第三次的二分题就不容易看出来了。给定一个有向图，每条边都有两种权值，时间和愉悦值。叫你寻找一条回路（不经过重复的边），使得愉悦值之和与时间总和之比最大。能想到这个题目是二分的话，那就真的很厉害了。二分最优比率C，然后给每条边设置一个新的权值，它等于C倍的时间减去愉悦值，再来判断是否有负权回路。这是怎么来的呢？不妨这样来看：对于任意一条回路，所求比率等于(Σ愉悦值)/(Σ时间)。如果二分出来的最优比率C偏小了，那说明满足(Σ愉悦值)/(Σ时间)>C的回路多得是，移动一下便有C*(Σ时间)-(Σ愉悦值)<0，即在新的权值设定下存在负权回路。如果没有负权回路的话，说明所有回路的比率都比C小，这就说明我们的C取大了。同样的思路也可以用来解决最优比率生成树问题。     第四次的二分题可就是真的牛B大发了。假设有一个长度为N的数组A_i，里面的每个数都不一样。但是呢，你不知道数组里的数是多少。给出若干个形如“从A_i到A_j中的最小值是x”的命题，问你第一个和前面有矛盾的命题在哪里。例如，给你四个命题：A_1到A_10的最小值是7，A_5到A_19的最小值是8，A_3到A_12的最小值是5，A_11到A_15的最小值是4。第三句话显然是错的，否则前两个区间中至少有一个的最小值也达到了5。     这个题难就难在，我们需要挖掘出“矛盾”的本质。究竟每一条命题给我们带来了什么信息呢？假设我告诉你，A_1到A_10的最小值是7，你仍旧不能推断出任何一个数，但有两点是肯定的：第一，这10个数里有一个数字7；第二，这里面的每个数都不能小于7。假设我们再给出一个A_5到A_19的最小值是8呢？此时，我们得知A_5到A_19里面有一个8，并且A_5到A_19的所有数都不小于8。注意！此时从A_5到A_10这一段中的数字下界升级了！由此得到启发，这些条件给出的信息说穿了就是每个位置可能出现的数的下界，它就是覆盖它的那些区间中的最大值。我们可以把区间端点排序，从左到右扫描一遍，用堆不断更新当前的最大值。在确定完每个位置可能的最小数后，我们开始寻找一个满足这些条件的解。由于数组中没有相同的数，因此对于所有回答“最小值为x”的区间，x必需出现在它们的交集中。如果这个交集为空，或者交集里面所有的位置（因下界过大）都不能取这个数，那么我们就可以肯定地说这一组条件是有矛盾的。如果我们顺利地给每个区间都安排好最小值所在位置，这立即说明了该组条件没有矛盾，因为我把其它那些没确定下来的位置取到无穷大，满足全部条件的数组就构造出来了。于是，我们有了一个O(nlogn)判断一组命题是否有矛盾的算法。     这个题有趣就有趣在，上述算法虽然高效，但却只能判断命题组是否矛盾，不能检测矛盾首次出现的位置；而在线判断命题是否矛盾（一个命题一个命题地往里面加）反而要慢些。于是呢，二分答案就派上用场了：二分前面的无冲突命题的最大长度，然后用上面的O(nlogn)算法来判断看是不是有矛盾。     然而，上面这些二分题都还太“正统”了一些。拼完了NOI之后，我便在网上自由潇洒地学习各种自己感兴趣的算法，看到了不少真正另类而绝妙的二分……