Find the nearest sum to a given number of two elements in sorted matrix

Question

Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest to a given value $q$. The restriction of memory is $\mathcal{O}(n)$. It is not allowed to change a given matrix.

The naive approach is $\mathcal{O}(n^4)$ brute force algorithm.

Also I can propose $\mathcal{O}(n^3)$ algorithm. Which use the following idea. Let we have two sorted arrays $c_1\leq c_2\le \cdots \leq c_{k}$ and $d_1\leq d_2\le \cdots \leq d_s$ and we need to find a sum of the form $c_i$ + $d_j$ nearest to a given $q$. We can do this by $\mathcal{O}(k+s)$ algorithm by imaginary merging two arrays: $$ c_1\leq c_2\leq \cdots \le c_{k}; \ \ q-d_s\leq q-d_{s-1}\leq \cdots\le q-d_{1} $$ in one array. So to solve the problem we can iterate the set of row-pairs of our matrix and to use the above idea. Of course this algorithm will have a complexity $\mathcal{O}(n^3)$.

My question. How can we do this more effectively?

Answer 1

Try something like binary search since it is sorted i.e. check a[n/2,n]+a [n/2 +1,1] if equal done -smaller check the lower half -greater check the upper half (Keep the last checked value to compare how close with the next one) Probably O ( log n2)