# How to solve this generalization of binary search?

Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.

Consider, for some unknown threshold $1\le T\le n$, a threshold function $$g(x)= \begin{cases} 0&\text{x<T}\\ 1&\text{otherwise}. \end{cases}$$

Our goal is to find $T$ while minimizing the worst case cost, where computing $g(x)$ for any $x\in\{1,\ldots n\}$ has a cost of $f(x)$. We assume that $f$ is known.

There are two straightforward approaches for this: a linear scan and a binary search.

It's not hard to see that each of them is good for different scenarios -- a linear scan works fine for $f(x)=2^{x}$ while a binary search is optimal for $f(x)=1$.

Since $f(n/2)$ may be much larger than $f(T)$, another approach is to use doubling and then binary search. The cost of this is bounded by $O(f(2T)\log T)$. This can be modified to $$O(\epsilon^{-1} f(T)\log T + f(T(1+\epsilon))\log (T\epsilon))$$ by doing the doubling using a $(1+\epsilon)$ factor.

If this problem is known, What is the name of this problem?

What is the optimal strategy here?

Obviously, it is possible to exhaustively compute the correct strategy. Can we compute it (or an approximation of it) faster? Is it possible to give an analytical formula for it?

I am aware that the problem is somewhat vague. Mainly, I am wondering if it is possible to analytically find an optimal solution (using the $f(i)$ values) and if not, if it is possible to compute a reasonable strategy given $f$ as an input. You may also assume additional reasonable properties on $f$.

The optimal strategy can be found through dynamic programming in $O(n^3)$ time. Let $A[i,j]$ denote the worst-case cost of the optimal strategy when $T$ is already known to be in $\{i,i+1,\dots,j\}$. Then we have the recursive relation
$$A[i,k] = \min \{f(j) + \max(A[i,j], A[j+1,k]) : j=i,i+1,\dots,k-1\},$$
with the base case $A[i,i] = 0$. You can use dynamic programming to fill out this array. The assumption that $f$ is non-decreasing is not needed; this works whenever $f$ is any non-negative function.
• It might be said that the $O(n^3)$ is a factor $O(n^2)$ for the number of entries in $A$ and a factor $O(n)$ to find the optimal $j$ in each step. Can the latter be found with binary search instead, in the $f$ is non-decreasing case, for a total runtime of $O(n^2\log n)$? May 18 at 20:24
• @AlbertHendriks, I don't immediately see how, but maybe you have some idea. The challenge I see is that $f(j)$ is a non-decreasing function of $j$ but $A[j+1,k]$ is a non-increasing function of $j$, so $f(j)+A[j+1,k]$ might not be a monotonic function of $j$, and I'm not sure how to deal with that.