This question already has answers here:
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 list对每一行和每一列进行排序，如下所示。
（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 list对每一行和每一列进行排序，如下所示。
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
最佳答案
显然，幼稚的解决方案是对每行（或列）执行二进制搜索，这将导致O（n log n）的运行时复杂度。
直接将二进制搜索应用于整个矩阵的主要问题是没有完全的排序。这使得很难定义一个“拆分元素”，其中“左”的所有元素都较小，“右”的所有元素都较大。
我的直接适应方法将更接近四叉树这样的空间索引。基本观察如下：对于原始矩阵的每个子矩阵，可以通过查看左上（下界）和右下（上界）元素来定义元素的边界。
现在基本上可以执行深度优先搜索，递归地将矩阵拆分为4个子矩阵，计算每个子矩阵的上下界，并根据键是否在其边界内丢弃或探索它。
关于algorithm - n ^ 2数组搜索算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48060611/