I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A_i$ is $\Theta(i^2)$. I do not directly care about the number of comparisons, I just want to minimize the sum of the costs of the comparisons in the expected case (worst-case would also be nice).

Let's assume that each element in $A$ is unique and that $A$ does not contain $c$.

What is the optimal algorithm?

  • $\begingroup$ Optimal in what sense? $\endgroup$ Commented Jul 24, 2018 at 16:59
  • 2
    $\begingroup$ @YuvalFilmus "to minimize the sum of the costs of the comparisons" $\endgroup$
    – koverman47
    Commented Jul 24, 2018 at 17:02
  • $\begingroup$ Can your element $c$ belong to $A$? Or does $c$ belong to one of the $|A|+1$ intervals created by removing the elements of $A$? Or perhaps, $c$ necessarily belongs to $A$? $\endgroup$ Commented Jul 24, 2018 at 17:03
  • $\begingroup$ $c$ could belong to $A$, but I have only binary comparison. Either $c \geq A_i$ or $c < A_i$. I want to find the $i$ where $c \geq A_i$ and $c < A_{i+1}$. Also, it is given that $c \geq A_0$ and $c < \max(A_i)$. $\endgroup$ Commented Jul 24, 2018 at 20:59
  • $\begingroup$ Actually $c$ belongs to $A$, but by my previous comment we can only find its index $i$ by comparing $c$ to both $A_i$ and $A_{i+1}$. $\endgroup$ Commented Jul 24, 2018 at 21:11

2 Answers 2


@Willard Zhan explains the asymptotic complexity.

If you want to optimize the constant factor, you can work out the optimal schedule of queries using dynamic programming. Let $B[i,j]$ denote the worst-case cost of the optimal strategy when $c$ is already known to be in the range $A[i]...A[j]$, and let $\text{cost}(i)$ denote the cost of comparing $c$ to $A[i]$. Then we have the recursive relation

$$B[i,k] = \min\{\text{cost}(j) + \max(B[i,j-1], B[j+1,k]) : j=i,i+1,i+2,\dots,k\}$$

with the base case that $B[i,k] = 0$ if $i \ge k$. The $B$ array can be filled in using dynamic programming, and from that you can compute the strategy whose worst-case cost is minimal. You can use a similar strategy ot compute the strategy whose expected cost is minimal; you just have to adjust the recursive relation above (the specific relation will depend on your assumptions on the distribution of $c$).

See also https://cstheory.stackexchange.com/q/40996/5038.

  • $\begingroup$ I accepted this answer as it works for every cost function, i.e. the general case. $\endgroup$ Commented May 11, 2021 at 12:06

Let's say I told you in advance that $c$ is in the larger half. You still need $\Omega(\log n)$ comparisons, while now every helpful comparison takes $\Omega(n^2)$ cost, so the cost is always $\Omega(n^2\log n)$, which can be achieved with simple binary search.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.