optimal search algorithm for finding parameters and thresholds

Question

I have the following problem:

There are $n$ variables $x_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'), and it is known that the test outcome only depends on a value of a single variable being larger than some threshold. That is, the outcome is 'Pass' if $x_k \ge c$ and 'Fail' if $x_k < c$. My goal is to find $k$ and $c$ (i.e. which variable is causing the failure and what is the threshold).

My thinking so far is as follows: if I know $k$ and only need to find $c$, than I can do a binary search and find the threshold in $\log_2 m$ steps. If I know $c$ and don't know $k$, I can similarly find it in $\log_2 n$ steps (by setting half of the variables to a value above the threshold and the other half to a value below, thus excluding half of the possibilities, etc.).

I can also first find $c$ in a similar way using a binary search, each time setting all the variables to the same value, and afterwards find $k$ as before. This will take a total of $\log_2 m + \log_2 n = \log_2 nm$ steps.

It seems however that this might not be the optimal approach. So my question is: Is there an algorithm that can find the answer in less than $\log_2 nm$ steps ?

(also, if someone has a suggestion for improving the title of this question, that would be welcome)

Answer 1

No, it's not possible to use fewer steps than that. Each test gives you one bit of information about the solution. There are $nm$ possible solutions, so you need $\lg(nm)$ bits of information to uniquely identify the solution -- which means you need at least $\lg(nm)$ tests.