3 ms·
But what if there are two (or more?) positive samples? It's an interesting problem.
by ced 6y ago
But what if there are two (or more?) positive samples? It's an interesting problem.
- bequanna 6y agoIf the initial test size is 64 and contains a positive, split into two groups of 32 and test each. Continue splitting and testing when a positive is encountered.
- ced 6y agoYeah, but this version is not necessarily optimal. If you have 4 positive samples, then you will test 2+2+1+1+1+1 = 8, instead of 4 in the naive case. It feels like a problem for information theory.
- gnulinux 6y agoYou keep binary searching each part. I.e. if both 32/32 subsamples turn positive, you perform binary search on those 32 samples.