language-agnostic - 搜索排序矩阵的最有效方法？

Question

我有一个作业要编写一个算法(不是用任何特定语言，只是伪代码)，该算法接收一个矩阵 [大小:M x N]，该矩阵的排序方式是所有行都已排序并且所有它的列单独排序，并在该矩阵中找到某个值。我需要编写我能想到的最省时的算法。

矩阵看起来像:

1  3  5
4  6  8
7  9 10

我的想法是从第一行和最后一列开始，简单地检查该值，如果它更大，则向下移动，如果小于，则向左移动，并继续这样做，直到找到该值或直到索引超出范围(如果该值不存在)。该算法的工作线性复杂度为 O(m+n)。有人告诉我可以用对数复杂度来做到这一点。是否可以？如果是这样，怎么办？

Answer 1

你的矩阵看起来像这样:

a ..... b ..... c
. .     . .     .
.   1   .   2   . 
.     . .     . .
d ..... e ..... f
. .     . .     .
.   3   .   4   .
.     . .     . .
g ..... h ..... i

并具有以下属性:

a,c,g < i  
a,b,d < e
b,c,e < f
d,e,g < h
e,f,h < i

因此最右最角落的值(例如i)始终是整个矩阵中最大的 如果将矩阵分成 4 个相等的部分，则该属性是递归的。

所以我们可以尝试使用二分搜索:

1. 探索值(value)，
2. 分成几 block ，
3. (以某种方式)选择正确的部分，
4. 转到 1 并添加新作品。

因此算法可能如下所示:

input: X - value to be searched
until found
 divide matrix into 4 equal pieces
 get e,f,h,i as shown on picture
 if (e or f or h or i) equals X then 
   return found
 if X < e then quarter := 1
 if X < f then quarter := 2
 if X < h then quarter := 3
 if X < i then quarter := 4
 if no quarter assigned then 
    return not_found
 make smaller matrix from chosen quarter 

这对我来说就像 O(log n)，其中 n 是矩阵中的元素数量。这是一种二分搜索，但是是二维的。我无法正式证明它，但类似于典型的二分搜索。