n ^ 2数组搜索算法[重复]

Question

这个问题在这里已有答案：

• find an element in a sorted matrix [duplicate] 9个答案
• Search a sorted 2D matrix [duplicate] 4个答案
• Most efficient way to search a sorted matrix? 9个答案
• Find number in sorted matrix (Rows n Columns) in O(log n) [duplicate] 5个答案

在排序数组中，我们可以通过二分搜索在O（logn）中搜索。但是我认为在n * n数组中，我们如何将这个算法（或其他）应用到数组中以便更快地搜索？ n * n列表按如下方式排列每行和每列。

  1  3  7 13 19
  2  5 12 14 20
  4  9 15 16 22
  8 10 18 23 25
 11 17 21 24 27

Answer 1

显然，天真的解决方案是在每一行（或列）上执行二进制搜索，这将导致运行时复杂度为O（n log n）。

我在直接调整二进制搜索到整个矩阵时看到的主要问题是没有完整的排序。这使得很难定义“分裂元素”，其中“左”的所有元素都较小，而“右”的所有元素都较大。

我直接适应的方法将更接近像四叉树这样的空间索引。基本观察如下：对于原始矩阵的每个子矩阵，您可以通过查看左上角（下边界）和右下角（上边界）元素来定义元素的边界。

现在，您基本上可以执行深度优先搜索，递归地分割4个子矩阵中的矩阵，计算每个子矩阵的上限和下限，并根据密钥是否在其范围内而丢弃或探索它。