3.2.2 先对一半的硬币进行考虑

我们现在需要从16枚硬币中找出假币，先把16枚硬币分成两份，每份分别含有8枚硬币，为了方便描述，我们把第一份称为实例A，第二份称为实例B。我们先比较实例A和实例B的质量，如果实例A比实例B轻，则实例A中存在假币；如果实例B比实例A轻，则实例B中存在假币；如果实例A和实例B的质量相等，则假币不存在。如果存在假币，我们继续取出质量较轻的分组，按照刚才的策略分成两份，取出较轻的分组……，不断重复下去，直到两个分组都只包含1枚硬币，无法再继续分组下去，这样我们也就找到了哪枚硬币是假币。本问题只有“分”和“治”，不需要“合”的过程。我们通过图例进行仔细讲解。

（1）首先我们先对一半的硬币进行考虑，将16枚硬币分成两份，如果不存在假币，那么两份的质量应该相等，如果某份质量较轻，那么假币一定在该份中，我们假设第一份包含了假币，如图3.3所示。

图3.3 16枚硬币分成两份

（2）我们再对较轻的一份，即第一份的一半硬币进行考虑，将8枚硬币再分成两份，如果存在某份质量较轻，那么假币一定在该份中，我们假设第二份包含了假币，如图3.4所示。

图3.4 8枚硬币分成两份

（3）我们再对较轻的一份，即第二份的一半硬币进行考虑，将4枚硬币再分成两份，如果存在某份质量较轻，那么假币一定在该份中，我们假设还是第二份包含了假币，如图3.5所示。

图3.5 4枚硬币分成两份

（4）我们再对较轻的一份，即第二份的一半硬币进行考虑，将2枚硬币再分成两份，每份仅包含1枚硬币，如果存在某份质量较轻，那么该枚硬币就是假币了，我们假设第一份包含了假币，如图3.6所示。

这样我们通过4次比较就找到了假币，通过分而治之算法找到假币的效率要比简单的两两比较效率高，分而治之算法的时间复杂度是O（logn）。

图3.6 2枚硬币分成两份