漫话二分法.doc

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