问题描述:给出27枚硬币,它们的各种外观完全相同,但有一枚硬币稍重一点,是假币,我们只有一杆秤,试找到一种便捷的方法找出假币。
简单直接的思路是:直接从头到尾扫描遍历一趟,找出最大的即可。算法复杂度是 O ( N ) O(N) O(N),不符合我们这一问题“尽可能少比较次数”的宗旨。
可以优化上述思路。 容易想到二分查找,进而用将硬币分为2堆+1个,“折半”比较,找出那个特殊的假硬币。
还可以继续优化。 我们可以随机等分成三份,拿出两组比较,划分的对称性更强,查找也更快。 比如9枚硬币,二分最坏的情况是3次查找;三分