Поиск двух элементов приближающих число в матрице

[arien]

Дана матрица $n \times n$, каждая строка и каждый столбец которой упорядочены по возрастанию. Предложите алгоритм, находящий два элемента этой матрицы, сумма которых наиболее близка к заданному числу q. Ограничение по дополнительной памяти — $O(n)$. Изменять исходную матрицу нельзя. Оценка будет зависеть от эффективности вашего алгоритма.

Собственно, понятно, что можно перебрать все пары чисел за $O(n^{4})$. Но сдается мне, что авторы задачи не этого хотят
Как думаете, насколько быстрым можно сделать алгоритм(и как)?
Также, если Вы знаете литературу, которая по вашему мнению может помочь мне прозреть, буду благодарна за ссылки.

[Brukvalub]

Тупой перебор не учитывает условия

arien в сообщении #1136190 писал(а):

каждая строка и каждый столбец которой упорядочены по возрастанию.

Упорядоченность элементов позволяет организовать что-то наподобие метода "вилки". Например, начать с суммы элементов из "середины" матрицы, тогда будет ясно, какие суммы заведомо не имеет смысла брать.

[mihaild]

Есть довольно очевидный способ за $O(n^3)$ (стандартный способ поиска элемента в матрице, упорядоченной по строкам и столбцам - смотрим в правый верхний угол, откидываем либо один столбец, либо одну строку).

[arien]

mihaild в сообщении #1136198 писал(а):

Есть довольно очевидный способ за $O(n^3)$ (стандартный способ поиска элемента в матрице, упорядоченной по строкам и столбцам - смотрим в правый верхний угол, откидываем либо один столбец, либо одну строку).

То есть идем по всем элементам матрицы, и для каждого ищем ближайший к q-$a_{ij}$ элемент за $O(n)$.. Да, это уже хорошо, но интересно, можно ли сделать быстрее?

[venco]

Если каждый раз искать с нуля то $O(n^3)$, но можно перебрать элементы по возрастанию за $O(n^2\ln(n))$ и с другой стороны - по убыванию за те же $O(n^2\ln(n))$. Для этого потребуется дополнительная память $O(n)$.