search in array with specific properties

Question

I have a 2D array in which values are monotonic. How to find all (x,y) where |f(X,Y) – v1| < t in best way.

Answer 1

Searching for a value in a matrix with sorted rows and columns is a classic problem. Initialize row to its maximum value and column to its minimum value. Examine the matrix entry at row, column. If it's less than the target value, then increase column by one. If it's greater than the target value, then decrease row by one. The number of matrix entries inspected is at most #rows + #columns - 1.

If this search is continued after the target value is found by decreasing row by one (respectively, increasing column by one), then we obtain as a byproduct a determination of which elements are less than (respectively, less than or equal to) the target value. Perform this search algorithm 2|V| times with different target values (less than or equal to v_i - t, less than v_i + t) to solve the problem with O(|V|n) matrix elements inspected.

Various optimizations are possible. The most obvious is to cache the matrix values. Another is, instead of stepping by just one, use unbounded binary search to determine the most appropriate increment/decrement. It's unclear in prospect whether the higher worst-case constant factor would be overcome by the savings resulting from large changes in neighboring entries.

Example using Mooing Duck's instance:

To look for elements in the range (48, 52),
  look for elements less than or equal to 48
    and (separately) elements less than 52.

Looking for elements less or equal to 48:
    Go right (>) if the current element is less than or equal to 48.
    Go down (v) if the current element is greater than 48

50   60   70   80   90  100
 v
40 > 51   60   70   80   90
      v
30   50   52   55   70   80
      v
30   40 > 45 > 46 > 51   52
                     v
30   40   42   45   50   51
                     v
30   40   41   44   49   50
                     v
                  done (access would be out of bounds)

The elements less than or equal to 48 are those in some submatrix containing
  an examined element found to be less than or equal to 48
    and elements to the left and below.