Binary search with alternative comparison cost
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.