我卡在了以下问题上:
给定一个大小为n2的int二维矩阵
mat
,其中n = 2k,搜索整数k。
矩阵的行和列是有序的。
如果我们将矩阵分成四个部分,每个部分也是有序的。例如,给定这个矩阵:
-4 -2 5 9
2 5 12 13
13 20 25 25
22 24 49 57
如果我们将它分成四个部分,可以看到第一个部分中的所有数字都小于或等于第二个部分中的数字。
为了得到一个高效的算法,我考虑在这两个维度上进行递归二分查找,但是它未能在之前的矩阵中搜索到"2"。
以下是代码:
public static boolean find(int[][] mat, int x){
return find2(mat, x, 0, mat.length-1,0, mat.length-1);
}
private static boolean find2(int[][] mat, int x, int lorow, int hirow,int locol,int hicol){
if(mat.length==0) return false;
if(lorow>hirow || locol>hicol) return false;
int midrow=(lorow+hirow)/2;
int midcol=(locol+hicol)/2;
if(mat[midrow][midcol] == x ) return true;
else if(mat[midrow][midcol] < x)
return find2(mat,x,lorow,midrow,midcol+1,hicol) || find2(mat,x,midrow+1,hirow,locol,midcol) || find2(mat,x,midrow+1,hirow,midcol+1,hicol);
else
return find2(mat,x,lorow,midrow,locol,midcol-1) || find2(mat,x,midrow,hirow,locol,midcol-1) || find2(mat,x,midrow+1,hirow,midcol+1,hicol);
}
请给予建议。