I have 100 objects, some of them are correct and the other could be incorrect.
I would like to find corrects only objects from the 100.
I have a function bool isCorrect(List<object> objs) (O(1)) that get x objects and return false if at least one object is incorrect - I can't change that function.
Every isCorrect call make a network request. So you would like to save requests.
What Iv tried?
1. Run each object isCorrect- O(n)
2. Run binary search - if 100 is return incorrect split to 50 50 and etc... - O(log2(N)).
The worst case is O(log2(N)) + O(N)
Can I find any other algorithm better than that?
This problem is output sensitive. Let's suppose your output is the list of sequences of objects that are correct, then the minimum complexity you can reach is Omega(length of this list).