二维数组的二分查找 - Java

Question

我卡在了以下问题上：

给定一个大小为n²的int二维矩阵mat，其中n = 2^k，搜索整数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);
}

请给予建议。

- Meni

---

相关问题（不带象限排序约束）：如何在从左到右和从上到下排序的二维数组中搜索数字？ - Bernhard Barker

Answer 1

你的错误在代码中的这里。

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);

在前两个函数中，您正在从搜索空间中删除中间列。您需要将其包含为元素可能出现在中间列。另一个错误在于最后一次调用find2（mat，x，midrow + 1，hirow，midcol + 1，hicol）。

如果您的搜索元素小于中间元素，则应选择中间元素的左上象限并忽略右下象限。您在这里错误地考虑了右下象限而不是左上象限。

相应地进行更改后，else中的返回函数如下：

return find2(mat,x,lorow,midrow,locol,midcol) || find2(mat,x,lorow,midrow,midcol+1,hicol) ||find2(mat,x,midrow+1,hirow,locol,midcol);

这个问题已经解决，它会返回true给-2。

更新后的代码：

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;

    if(lorow==hirow && locol==hicol && mat[lorow][locol]!=x)
        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) || find2(mat,x,lorow,midrow,midcol+1,hicol) ||find2(mat,x,midrow+1,hirow,locol,midcol);
}

- Sanket Makani

---

非常感谢你，朋友。但是你的代码有一个错误。例如，如果你输入0或者一个比矩阵中第一个数字更小的数字（如-6），就会出现堆栈溢出错误。 - Meni

@Meni，是的，那个条件还需要检查。你可以将其添加到终止递归调用中。 - Sanket Makani

Answer 2

如果您的矩阵行和列已排序，则可以使用以下代码。

public int search(int mat[][], int n, int x) {
        int i = 0, j = n - 1;
        while (i < n && j >= 0) {
            if (mat[i][j] == x) {
                System.out.println("Found at" + i + j);
                return 1;
            }
            if (mat[i][j] > x)
                j--;
            else // if mat[i][j] < x
                i++;
        }

        System.out.println("not Found at");
        return 0;
    }

- gati sahu

---

感谢您的评论，但是您的答案与我的问题无关。您的代码复杂度为O(n^2)，这并不好。 - Meni

我认为它是O(n)，对于mn矩阵，它将是O(m+n)。你能否解释一下如何变成O(nn)？ - gati sahu

对不起，我的意思是它的时间复杂度是O(n)，但我想要达到的答案是O(log(n))。 - Meni

@gati sahu，你的代码有 bug。int[][] data = { {10,20,30,40}, {15,25,35,45}, {27,29,37,48}, {32,33,39,50} }; 它无法找到在2,3位置上存在的33。 - Mr code.