二叉树算法变异:如果每个组都有有限的元素，如何进行搜索？

Question

考虑到n中有一个人携带病毒。这种测试可以在血液样本中进行，在这些血样中，小部分人的血液混合在一起，但至多是k人的血液可以混合在一起。同时应用k人血样检测k^(1/2)

我想到的算法是：

when n = 1 return the person 
First divide the groups into n/k, so that k people are in each group 
test each group  
if(group i contains a virus) 
   binary search(group i) 

但是，我不知道如何把总成本降到最低。我相信，如果k更接近于n，就会付出最小的代价，但这只是我的直觉，没有任何证据。是否有一个更有效的算法将花费最小？

Answer 1

最小化测试成本的最佳方法是将测试组排列成一个正方形，将每一行的所有样本混合成一个样本，将每个列中的所有样本混合成一个样本并进行测试。根据结果，可以识别行和列，并可以识别特定的示例。

如果sqrt(n)

1 2 3
4 5 6
7 8 9

目前共有6个样品R1、2、3、R4、5、6、R7、8、9、C1、4、7、C2、5、8、C3、6、9，并根据结果构建了结果。如果R1，R2为正，C1 & C2为正，则1,2,4,5为正。

如果sqrt(N) >K，则将N划分为N/K^2组的K^2元素，并进行同样的划分。