Find the nearest sum to a given number of two elements in sorted matrix Given a sorted  $n\times n$ matrix $A$ of real values. That is $a_{ki}&lt;a_{kj}$ and $a_{it}&lt;a_{jt}$, when $i&lt;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?
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)