<p>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</p>

<p>$$A[i,k] = \min \{f(j) + \max(A[i,j], A[j+1,k]) : j=i,i+1,\dots,k-1\},$$</p>

<p>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.</p>

CC BY-SA 4.0
2021-05-18T20:24:05.513Z
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)$?
Albert Hendriks
CC BY-SA 4.0
2021-05-18T21:32:04.177Z
@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.
D.W.
CC BY-SA 4.0
2018-06-14T19:40:33.850Z
2018-06-14T19:40:33.850Z
D.W.
<p>Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.</p>

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

<p>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.</p>

<p>There are two straightforward approaches for this: a linear scan and a binary search.</p>

<p>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$.</p>

<p>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.</p>

<blockquote>
  <p>If this problem is known, What is the name of this problem?</p>
  
  <p>What is the optimal strategy here?</p>
</blockquote>

<hr>

<p>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?</p>

<p>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$.</p>

<ds.algorithms><reference-request>
How to solve this generalization of binary search?
R B
# How to solve this generalization of binary search?

(Asked by: username_0 on 2018-06-14)

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

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$.

**Tags:** ds.algorithms, reference-request

---

## 1 answers

### Answer by username_1 on 2018-06-14. Score: 3

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.

> **Comments:**
> **username_2**: 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)$?  
> **username_1**: @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.  

---

