2
$\begingroup$

There is a way for finding K entries of N given entries using a binary search?

I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint.

The naive way is to iterate one after one and check whether it answers the condition or not. The naive way of Binary Search is using A Binary search until it covers all the tree, this method have a running time $O(K \log n)$. In this way, I will check whether half of the entries answer the condition or not, if they are I will keep investigating the half of the half and so on. It's possible to make it more efficient with saving a dictionary from state to its answer. However, what will be its running time?

Example - Let's say I have a system and I want to check whether deleting some file corrupt it. The naive way is to delete file after file and to check whether the system behaves normally after each deletion. In Binary search, we can index the files from 0 to N-1 and delete each time half of the files. After each deletion, we can check whether the system behaves normally or not. If it behaves normally, the files we deleted in this step do not affect the system. If not, At least one of the files that were deleted affect the system. I asked, how can I find K files that affect the system?

Thanks.

$\endgroup$
  • 2
    $\begingroup$ Binary search only works for sorted arrays. Perhaps you’re not describing the complete picture? $\endgroup$ – Yuval Filmus Aug 26 '19 at 14:07
3
$\begingroup$

Your problem is known as group testing. An essentially optimal algorithm for your problem is Generalized binary splitting. There are also pretty good non-adaptive algorithms (such algorithms fix all queries ahead of time).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In my domain K (Number of files that affect the system) is not given. However, in Generalized binary splitting K is given. Do you have any idea how can I deal with this? Thanks. $\endgroup$ – Noam Moskovich Aug 29 '19 at 8:56
  • $\begingroup$ I suggest taking a look at the extensive literature on group testing. $\endgroup$ – Yuval Filmus Aug 29 '19 at 8:57
  • $\begingroup$ One thing you could do is run the algorithm for $k=1,2,4,8,\ldots$ until you find all entries. This is optimal up to constant factors. $\endgroup$ – Yuval Filmus Aug 29 '19 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.