Очевидно, что во время работы указатель сдвигается максимум на n строк и m столбцов. В этом случае время работы составляет <tex>O(n + m)</tex>.
==Решение за O(log^2(n))==
Идея решения за O(<tex>(log(n))^2</tex>) основана на принципе "разделяй и властвуй".
===Идея решения===
1) Выбираем центральную строку или столбец в матрице (middle), по которому мы будем перемещаться. Используя линейный поиск, необходимо найти такое значение i, что выполняется следующее условие: <tex>a[middle][i] < target < a[middle][i+1]</tex>.
