Imagine you're given an array $$$A$$$ of length $$$n$$$ and you're required to find the largest subset of this array that satisfies a certain condition. Let's assume that the given condition makes the problem $NP-$complete and also allows the following to be true:
If there exists a subset of length $$$k$$$ that satisfies the given condition, then assuming that $$$k > 1$$$, there necessarily exists subsets of length $$$l$$$, $$$1 \le l < k$$$, that satisfies the condition.
If there does not exist a subset of length $$$k$$$ that satisfies the given condition, then assuming $$$k < n$$$, there necessarily will not exist any subset of length $$$l$$$, $$$k < l \le n$$$, that satisfies the condition.
In short, the binary search property holds.
Since the problem is $$$NP-$$$complete, however, there exists no efficient function that allows us to find whether there exists a subset of length $$$k$$$ that satisfies the condition or not. So the only thing we can do is iterate over all subsets of length $$$k$$$ and check whether each of them satisfy the given condition or not. The time complexity of this function would then be $$$O(n * \binom{n}{k})$$$.
My question is, if we use binary search on this problem armed with the brute force function mentioned above, what would the time complexity of this algorithm be in the worst case? I imagine there would be a significant speed-up since we would be evaluating the function only a logarithmic number of times, as opposed to ordinary brute force search where we would evaluate that function at all possible values of $$$k$$$ (by iterating through all the subsets of $$$A$$$), but not enough to give us a polynomial time algorithm.
For example, you can consider the set cover or vertex cover problems (in both of these problems we're required to find the smallest subset satisfying the given condition however, not the largest).
