# Binary search with alternative comparison cost

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?

• Optimal in what sense? Jul 24, 2018 at 16:59
• @YuvalFilmus "to minimize the sum of the costs of the comparisons" Jul 24, 2018 at 17:02
• 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$? Jul 24, 2018 at 17:03
• $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)$. Jul 24, 2018 at 20:59
• 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}$. Jul 24, 2018 at 21:11

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