对1000个人二进制编码,2^10 = 1024, 需要10bit, 派10个人每个人负责检验出一个bit,每桶酒的编码中,该bit为1表示喝,0表示不喝,检查结果的方法是,10人中死了的代表喝过毒酒,检测出毒酒的该bit为1,这样就可以检测一次找到毒酒的编号。
如果说这个与二分法有何关系的话,可以看作,是10个人同时对1000桶酒进行了一次分割, 即并行的二分法,与传统意义上的二分法不同。
再仔细思考一下,为何此题的情形中使用并行的二分分割,而普通问题如:查找一个排序数组中的某个数字,不使用并行分割的方式呢?因为题目中从检测到出结果要等待的时间太久了(也可以说,代价很大),而普通问题(从比较两个数到得到比较结果)不存在这种问题,其实单看试毒(或普通问题中的“比较”)次数,并行的二分其实与线性搜索一样,而传统的二分查找则是lgn,不过传统的二分查找每次比较都依赖于上一次比较的结果,考虑到本题的特殊性,当然就不可取了。 |