高效的分治：二分查找法

在遇到复杂问题时，通常会考虑将这个问题进行划分，划分后的子问题又是规模更小的原问题，而划分后的子问题的解答可能是非常直观的，或是非常容易得到的，当子问题解决以后原问题也就解决了。这就是分治的基本思想。

(1)二分查找

查找也称检索。计算机最重要的功能之一就是在浩瀚的数据中找到用户所要的信息。但是计算机的速度还并没有快到能瞬间完成这一过程的程度，而且等待计算机查找的数据集往往是异常庞大的，因此我们需要更快捷、更有效的搜索方式。最直观的查找方法就是顺序查找，计算机进行搜索时从储存数据的开头开始找，直到找到指定数据时结束查找。这种查找对计算机来说是非常慢的。如果所有待查找的数据元素按递增(或递减)有序，则可以采用二分查找。这是一种使用了分治思想、效率较高的查找方法。

二分查找是如何找到待查数据的呢?我们还是来看看生活中曾经见过的例子。在一些电视综艺节目中出现过“价格竞猜”的游戏环节。主持人开始给出某一商品的价格范围，参与者说出一个价格，然后主持人会告知猜的价格是高了还是低了，参与者进行下一轮竞猜。很显然，每次竞猜完毕后，商品价格范围就缩小了，下次的竞猜一定是在这个较小的范围内进行。假如一开始设定的竞猜价格范围是0到100，比较明智的做法是:参与者首先猜想价格为50，如果主持人告知价格猜高了，下次竞猜价格就在0到49之间进行；反之，如果价格猜低了，就在51到100之间进行下次竞猜；如此反复进行，直到猜到商品的具体价格为止，这就是二分查找的思想。因为不知道商品的具体价格，在开始给出的价格范围内的任何一个数值都可能是商品的具体价格，参与者要做的就是在0到100之间查找到表示商品真实价格的数据。这和在一批数据中进行指定数据的查找是一样的。需要注意的是，二分查找效率虽然较高，但必须先将待查找数据进行排序——这是二分查找方法的前提条件或代价。

(2)递归

在日常生活中，字典就是一个递归问题的典型实例。字典中的任何一个词都是由“其他词”解释或定义的，但是“其他词”在被定义或解释时又会间接或直接地用到那些由它们定义的词。

数学中阶乘的定义是n!＝n×(n－1)×(n－2)×…×2×1，其实，也可以用递归的思想定义正整数n的阶乘，将它写成n!＝n×(n－1)!。在计算时，可以利用(n－1)!来计算n!，同理再用(n－2)!来计算(n－1)!，即(n－1)!＝(n－1)×(n－2)!，以此类推，直到用1!＝1逆向递推出2!，再依次递推出3!、4!、…、n!时为止。(www.xing528.com)

当用递归的方法解决问题时，显然不能像字典那样，词A的含义用词B来解释，而词B又用词A来解释，字典之所以可以这样做是由于事先假设使用者在词A和词B中至少有一个的含义是了解的。要想解决实际问题需要像数学中求阶乘的递归方法一样，才能真正解决问题。因此，要想使用递归解决问题必须满足以下两个条件。

①由其自身定义的与原始问题类似的更小规模的子问题。它使得递归过程持续进行(例如递归求阶乘中，n＞1时，n!＝n×(n－1)!，只要将(n－1)!求出来，n!也就求出来了，这样就将问题的规模缩小了)。

②递归的最简形式。它是一个能够用来结束递归过的条件(例如递归求阶乘中，n＝1时，直接求解n!＝1)。

对于一些复杂问题，直接求解的难度非常大，但是分析以后用递归的方法来解决就非常简单直观了。

第4章习题