搜索排序的二维矩阵

问题描述：

M是整数的二维矩阵（n×m个）它们被分类在两行和列写一个函数搜索（int类型）返回的数量或空的确切位置。什么是最有效的方法来做到这一点？

M is a 2D matrix of integers (nXm) they are sorted in both row and column Write a function search(int s) that return the exact location of the number or Null. What would be the most efficient way to do so?

答

初始化：M [1..1（行），1 .... M（列）]

init: m[1..n(rows),1....m(columns)]

我= N，J = 1

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或我是出界回输步骤没有解决方案。

at each step if j or i is out of bound return no-solution.

在此解决方案的复杂度为O（N + M）的情况下，N = M的复杂度为O（n）

The complexity of this solution is O(n+m) in case n=m the complexity is O(n)

我不知道是否有一个日志（N * M），如二进制搜索解决方案

I wonder if there is a log(n*m) solution like in binary search

修改另一种可能的解决方案：

EDIT another possible solution:

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）

I am not sure about the efficiency of this solution: if R = N*M then T(R) = T(R/2) + T(R/4) + O(1)

搜索排序的二维矩阵

相关推荐