3.2.3 找出硬币的规律

通过上一节的图解，读者朋友应该找到了通过分而治之算法找出假币的规律，硬币问题本质就是二分搜索，通过不断的两两比较，直到找到假的硬币。那么接下来我们进行实战编程，通过程序来帮助笔者从16枚硬币中找到假币。完整代码如下。

找出假币的程序运行结果如图3.7所示。

图3.7 找出假币的程序运行结果

可以发现，程序的运行结果和分析结果是一致的，我们已经成功地通过程序帮助笔者找到了那枚假币。接下来我们对程序重要的数据结构和方法进行讲解。

首先我们要定义一个硬币类，该硬币类应该包含如下信息：硬币的名字及硬币的质量，如下所示。

在查找硬币的过程中，总会将硬币分成两份，然后比较每份的质量，获取每份的质量代码如下所示。

如果两份硬币质量相等，则硬币中没有假币，如果存在假币，则一定是在质量较轻的那份中，按照刚才的策略继续分成两份，取出较轻的那份……不断重复下去，直到两份都只包含1枚硬币，无法再继续分下去，这样我们也就找到了哪枚硬币是假币，代码如下所示。