7.5折半法的运用
通过前面的例子，我们已经认识了翻番的威力：一个很小的数，经过多次翻番后，很快就会得到一个非常大的数，如7.4节中舍罕王的赏赐，经过63次翻番，从最初的数字1增长成一个天文数字。通过这些例子，我们已经知道翻番的运算是很简单的，就是将前期的数据乘以2，即可得到本期数据。
7.5.1 翻番的逆运算
翻番的逆运算也很简单，就是将前期的数据除以2，用来得到本期数据，这种计算方法称为折半法，也称为二分法。
根据翻番运算的规则我们可以推出，对于原本很大的数据，通过多次折半运算后，可以得到一个较小的数据。
在实际应用中，将某一个很大的数进行折半运算以得到一个较小数据的情况不是太多。不过，在程序设计中，经常会用到一种查找算法：折半查找法。这种算法就是将原来需要处理的数量很庞大的一组数据，通过折半运算不断缩减运算规模，以方便、快速地查找出需要的数据。
例如，原来要在10亿组数据中查找某一个数，如果逐个去比较这些数据，最坏的情况下，需要进行10亿次比较才能找到需要的数据。而如果使用折半运算，第一次折半运算就可以将问题规模缩减为5亿，再次折半运算又可缩减为2.5亿，经过多次折半运算，很快就可以问题规模缩减到个位数，并找到目标数据。
因此，在程序设计中，折半运算在数据查找类运算中应用十分广泛。
7.5.2 找出假硬币
下面我们来看一个小学生常见的智力题：找假硬币。
现有100枚硬币，知道其中有1枚是假的，不过，由于假硬币的外观与真硬币完全一样，凭肉眼无法分辨。但是由于使用的材质不同，假硬币的重量比真硬币的重量轻。现在用一个天平作为工具，从这100枚硬币中找出那1枚假硬币，问：最少经过多少次称重必定能找出那枚假硬币？
看起来这个问题很简单，就是找出假硬币，但是，要求用最小的次数且必须找出假硬币。
在这道题中，只有天平这一个工具可以使用，因此，只能通过称重的方法来找出假硬币。虽说只有称重这一方法，可是怎么称重又可以分很多种情况。
1．逐个称重
要通过天平这个工具找出假硬币，最简单易懂的方法就是：用天平逐个称出每枚硬币的重量并记录下来，然后从这些记录中找出重量最轻的那枚就是假硬币。
最理想的情况是，称第1枚和第2枚重量时，就发现这两枚硬币的重量不一样，这时就可知道重量轻的那枚为假硬币。也就是说，通过称重2次就可找出假硬币。
最坏的情况是，对第100枚硬币进行称重时才发现其重量比其他硬币轻，即需要经过100次称重才能找出假硬币。
显然，这种方法的效率不会让人满意。
2．折半称重
根据前面提到的折半运算方法可将问题规模快速缩减，对于这个问题，就可考虑使用折半运算的方法，即将100枚硬币进行折半运算，可分为两部分，每一部分为50枚，然后分别对这两部分硬币进行称重。可以知道，重量轻的那部分中就包含有假硬币。接着对包含假硬币这部分（共50枚硬币）再次进行折半运算，又分为两部分，每一部分25枚，再通过称重找出假硬币在哪一部分并不断重复进行折半运算，最终即可找出假硬币。
由于使用天平进行称重，因此，可以将折半运算分成的两部分硬币分别放在天平的两边。也就是说，每次折半运算，只需要称重一次就可发现假币在哪一部分中，不需要对折半分出的两部分硬币分别称重。这样，可减少称重的次数。
根据以上思路，折半称重的过程如图7-8所示
图7-8
从图7-8中可看出，经过6次称重，必定能找出那枚假硬币。在最理想的情况下，第3次称重就可找出那枚假硬币。
第1次称重时，将100枚硬币分成两部分，天平的左边放50枚，右边放50枚。如果天平右边秤盘中的硬币较轻，说明那枚假硬币位于右边秤盘中。
第2次称重时，将右边秤盘中的50枚硬币又分成两部分，左边放25枚，右边放25枚。如果天平左边秤盘中的硬币较轻，说明那枚假硬币位于左边秤盘中。
第3次称重时，由于25枚硬币不能进行平均折半分到两个秤盘中，这时可在左边放12枚，右边放12枚，剩余1枚。这次称重就会有3种情况：第一，如果天平秤盘两边的重量相等，说明剩余的1枚为假硬币，完成称重；第二，如果右盘秤盘中的硬币较轻，说明那枚假硬币位于右边秤盘中；第三，如果左边秤盘中的硬币较轻，说明那枚假硬币位于左边秤盘中。
第4次称重，若第3次称重未找到假硬币，则将假硬币所在秤盘中的12枚硬币再次折半分到两个秤盘中，左边放6枚，右边放6枚，如果天平左边秤盘中的硬币较轻，说明那枚假硬币位于左边秤盘中。
第5次称重，若第4次称重未找到假硬币，将6枚硬币折半分到两个秤盘中，左边放3枚，右边放3枚，如果天平右边秤盘中的硬币较轻，说明那枚假硬币位于左边秤盘中。
第6次称重，若第5次称重未找到假硬币，与第3次类似，将3枚硬币分成3份，左边放1枚，右边放1枚，剩余1枚。这次称重就会有3种情况：第一，如果天平秤盘两边的重量相等，说明剩余的1枚为假硬币；第二，如果右盘秤盘中的硬币较轻，说明右边秤盘中的为假硬币；第三，如果左边秤盘中的硬币较轻，说明左边秤盘中的为假硬币。
3．三分称重
在图7-8所示折半称重的方法中，第3次和第6次称重时，都是将硬币分为了3部分，如果在天平左右秤盘上的两部分相等，则说明假硬币在第3部分中。那么，如果我们每次都将硬币分为3部分进行处理，会不会减少称重的次数呢？
答案是：在特定的条件下，这种三分称重可以减少称重次数。
具体的特定条件是什么呢？就是硬币的数量为3n时，可使用这种三分称重法。
例如，当80枚真硬币中混入1枚假硬币（共81枚硬币）时，就可使用这种三分称重法，具体过程如图7-9所示。
图7-9
从图7-9中可看出，对于81枚硬币，当采用三分称重法时，只需要称重4次就可找出假硬币
第1次称重时，将81枚硬币均分为3部分，天平左边放27枚，右边放27枚，剩余27枚。这时将有3种情况：第一，天平两边的硬币重量相等，则假硬币在剩余的27枚中。第二，天平左边硬币重量较轻，则假硬币位于左边27枚中。第三，天平右边硬币重量较轻，则假硬币位于右边27枚中。
第2次称重时，将27枚硬币均分为3部分，天平左边放9枚，右边放9枚，剩余9枚。同样按3种情况来确定假硬币所在的部分。
第3、4次称重时类似，都是将假硬币所在部分均分为3部分，其中2部分放在天平左右秤盘中，1部分剩余。直到折半到只有1枚硬币时就可直接找出假硬币了。
如果按折半方法来查找假硬币，则其查找过程如图7-10所示，与100枚硬币相似，最多需要6次称重。在理想情况下，称重1次，就可找出假硬币（为剩余的那枚）。
图7-10
虽然使用三分称重的方法可以减少称重的次数，但那是有条件的，即硬币的数量需要为3n。对于不满足这个条件的情况，则没办法使用这种方法。
7.5.3 编写程序找出假硬币
前面我们介绍了用称重法找出假硬币的过程，可以看出，使用折半运算是最方便、快速的方法（虽然用三分称重法可减少称重次数，但有特殊的限制条件）。
下面，我们编写一个程序来模拟这种折半称重。在程序中，通过随机函数模拟生成一枚假硬币，并使其重量比真硬币轻。然后程序模拟折半称重的过程，对任意数量的硬币进行模拟操作，并找出假硬币所在序号，具体代码如下：
以上代码右侧有详细的注释，可看出程序是完整模拟折半称重的过程。编译运行以上程序，可看到如图7-11所示的运行结果。当然，由于程序中使用随机序号作为假硬币的序号，因此，每次运行的结果都不一样。要查看程序运行结果是否正确，应将上面程序代码中注释掉的那一行启用，以显示生成的随机序号数值，用来和最终称重结果进行比对，看程序运行是否正确。在图7-11中，随机函数生成的序号是60，经过程序运算找出的也是第60枚为假硬币——由于C语言数组是从0开始的，因此，这里其实是第61枚硬币为假的，所以输出时将其加1，显示为61（表示在1～100枚硬币之间，第61枚硬币为假硬币）。
图7-11
7.5.4 折半法在查找中的应用
其实，折半法在查找算法中应用得更多，在查找算法中折半查找又称为二分查找。对于大批量数据，使用折半查找可以大幅提高查找的效率。
需要注意的是，要使用折半查找算法，被查找的数据必须要满足以下两个条件：
被查找的数据是线性结构保存的。
被查找的数据是按关键字有序排列的。
折半查找算法的具体过程如下：
假设有n个元素的查找表（要查找的源数据），首先计算位于查找表中间位置元素的序号m（m＝n／2），取s[m]的关键字与给定值key进行比较，比较结果有3种可能：
（1）若s[m]＝key，表示查找成功，找到所查关键字的位置m。
（2）若s[m]＞key，表示关键字key只可能在查找表的前半部分（因查找表中的数据是按从小到大的顺序排列），则在前半部分继续进行折半查找。
（3）若s[m]＜key，表示关键字key只可能在查找表的后半部分，则在后半部分继续进行折半查找。
可以看到，与前面进行折半称重类似，每经过一次查找，就将被查找数据的范围缩小一半。通过多次查找后，可将查找范围缩小到一个数据，最终可比较这个数据是否为要查找的关键字。
在查找中，并不能保证所查找的关键字必定在被查找数据中存在，当查找范围缩小到只剩下一个元素，而该元素仍与关键字不相等时，则说明查找失败。
根据前面的描述，我们先手工演示一下查找过程。例如，在以下10个数据，要求查找出关键字65所在位置的序号。
用折半查找法查找关键字65，查找过程如下：
从上面的查找过程可看出，通过4次比较，可找到关键字65所在的位置。
在上面这10个数据中，如果要查找关键字50的位置，其查找过程如下：
从上面的过程可看出，通过4次比较，当查找范围缩小到只剩一个元素，仍没有找到指定关键字，则说明查找失败。
根据以上对折半查找法的描述，可编写如下折半查找程序。
这段程序的代码很简单，与前面折半称重的程序类似，编译运行以上代码，输入查找关键字“65”，将得到如图7-12所示的结果。
图7-12