1
$\begingroup$

There is a way for finding K entries of N given entries using a binary search? I mean, I have N entries that indexed from 0 to N-1 and I have to find K of them that answer some condition. 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, that's will be O(Klogn). 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
  • $\begingroup$ Maybe describing the condition to be satisified will help. $\endgroup$ – Navjot Waraich Aug 27 '19 at 14:57
  • $\begingroup$ @YuvalFilmus Let's say you have a system and you 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? $\endgroup$ – Noam Moskovich Aug 28 '19 at 22:58
  • $\begingroup$ You should update the question with this information. $\endgroup$ – Yuval Filmus Aug 29 '19 at 5:04
  • $\begingroup$ @YuvalFilmus Done. $\endgroup$ – Noam Moskovich Aug 29 '19 at 8:57
0
$\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).

$\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.