在具有特定属性的数组中搜索

Question

我有一个2D数组,其中值是单调的.如何找到所有(x,y)其中| f(X,Y) - v1 | <t以最好的方式.

Answer 1

在具有排序行和列的矩阵中搜索值是一个经典问题.初始化row为其最大值和column最小值.检查矩阵条目row, column.如果它小于目标值,则增加column1.如果它大于目标值,则减row1.检查的矩阵条目数最多#rows + #columns - 1.

如果在通过减小row1(分别增加column1)找到目标值之后继续该搜索,则我们作为副产品获得哪些元素小于(分别地,小于或等于)目标值的确定.执行此搜索算法2 | V | 使用不同目标值(小于或等于v_i - t,小于v_i + t)的时间来解决检查O(| V | n)矩阵元素的问题.

可以进行各种优化.最明显的是缓存矩阵值.另一种方法是,使用无界二进制搜索来确定最合适的增量/减量,而不是只用一步.目前还不清楚是否可以通过邻近条目的大幅变化带来的节省来克服较高的最坏情况常数因子.

使用Mooing Duck的实例示例:

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.