3 ms·
You can do a binary search to efficiently locate the positive sample.
by douglaswlance 7y ago
You can do a binary search to efficiently locate the positive sample.
- ced 7y agoBut what if there are two (or more?) positive samples? It's an interesting problem.
- bequanna 7y 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 7y 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 7y agoYou keep binary searching each part. I.e. if both 32/32 subsamples turn positive, you perform binary search on those 32 samples.
- timerol 7y agoNote that optimal branch factor would probably depend on the expected negative rate. If 98% of your samples are coming back negative, it may be more optimal to divide by into 4 or 8 groups instead of 2 groups.