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

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

矩阵看起来像：

1  3  5
4  6  8
7  9 10

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

你的矩阵看起来像这样：

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. 探索价值，
2. 分成几块，
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 是矩阵中的元素数量。这是一种二分搜索，但是是二维的。我无法正式证明它，但类似于典型的二分搜索。