搜索已排序的2D矩阵

Question

M是整数的二维矩阵(nXm),它们在行和列中排序写一个函数搜索(int s),它返回数字或Null的确切位置.最有效的方法是什么？

Answer 1

init:m [1..n(行),1 .... m(列)]

i = N时,J = 1

从(i,j)开始:

STEP 1) if the value equals m(i,j) return (i,j)
STEP 2) if the value > m(i,j) go to step 1 with j+=1
STEP 3) else go to step 1 with i-=1

如果j或i超出范围,则在每一步返回无解.

在n = m的情况下,该解决方案的复杂度为O(n + m),复杂度为O(n)

我想知道是否存在二进制搜索中的log(n*m)解决方案

编辑另一种可能的解决方案

STEP 1)take the middle (n/2,m/2) of the matrix and compare it to the value
STEP 2) if the value equals m(i,j) return (i,j)
STEP 3) if the value is higher you can get rid from the first quarter  
STEP 4) if the value is lower you can get rid from the forth quarter
STEP 5) split the 3 other quarters to 2, a rectangle and a box, 
        send those both items to step 1 in a recursive manner

我不确定这个解决方案的效率:如果R = N*M则T(R)= T(R/2)+ T(R/4)+ O(1)