[ced]

But what if there are two (or more?) positive samples? It's an interesting problem.

[bequanna]

If 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]

Yeah, 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.

[bequanna]

I didn’t say it was optimal, but it is a huge improvement on doing 64 tests for 64 samples.

[ced]

Oh, sure!

[gnulinux]

You keep binary searching each part. I.e. if both 32/32 subsamples turn positive, you perform binary search on those 32 samples.