# Extend binary search

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.

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

• 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. – Yuval Filmus Aug 29 '19 at 8:58