java - 搜索二维排序矩阵部分，如果我在 O(n) 上完成，则需要进行代码审查

Question

我们有一个任务:

“编写一个有效的算法，在 n x n 表(二维数组)中搜索值。该表按行和列排序 - 即，表[i][j] ≤ 表[i][j + 1]，表[i][j] ≤ 表[i + 1][j]"

如果有人可以检查我的代码并看看我是否处于 O(n) 状态，或者我可以使我的代码更加高效。谢谢。

public static boolean find(int [][]a, int x)  // Efficiency O(n)
{

    if(a.length == 0 || a.length != a[0].length) // check if the matrix is squared or empty
        return false;


    int row = 0, col = a.length-1; // setting coordinates

    while(row < a.length && col >= 0) // running while the coordinates in bounce 
    {
        if (x > a[row][col])    // the "x" is bigger then my current spot, go down 1 row
            row++;
        else if(x < a[row][col])    // // the "x" is smaller then my current spot, go back 1 col
            col--;
        else
            return true;    
    }
    return false;

Answer 1

这是我的粗略草图，但它可以改善您的搜索。我尝试从二维数组中进行二分搜索。希望对您有帮助

static int moves = 0;

public static boolean find1(int[][] a, int x) // Efficiency O(n)
{

    if (a.length == 0 || a.length != a[0].length) // check if the matrix is squared or empty
        return false;

    int row = 0, col = a.length - 1; // setting coordinates

    while (row < a.length && col >= 0) // running while the coordinates in bounce
    {
        moves++;
        if (x > a[row][col]) // the "x" is bigger then my current spot, go down 1 row
            row++;
        else if (x < a[row][col]) // // the "x" is smaller then my current spot, go back 1 col
            col--;
        else
            return true;
    }
    return false;
}

public static boolean find(int[][] a, int x) // Efficiency O(n)
{

    int row = findRow(a, x);
    print(row);
    if (row < 0)
        return false;
    int col = findCol(a[row], x);
    print(col);
    if (col < 0)
        return false;
    return true;
}

public static int findRow(int[][] a, int x) {
    int row = a.length;
    int start = 0, end = a.length - 1;
    while (start <= end) {
        moves++;
        int current = start + (end - start) / 2;
        if (a[current][0] <= x && a[current][a[current].length - 1] >= x) {
            return current;
        } else if (a[current][a[current].length - 1] < x) {
            start = current + 1;
        } else {
            end = current - 1;
        }
    }
    return -1;
}

public static int findCol(int[] a, int x) {
    int start = 0, end = a.length - 1;
    while (start <= end) {
        moves++;
        int current = start + (end - start) / 2;
        if (a[current] == x)
            return current;
        if (a[current] < x)
            start = current + 1;
        else
            end = current - 1;
    }
    return -1;
}

public static void main(String[] args) throws Exception {
    int[][] a = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 },
            { 21, 22, 23, 24, 25 } };
    print(find(a, 21));
    print(moves);
    moves = 0;
    print(find1(a, 21));
    print(moves);
}

打印函数只是System.out.println()，我只是懒;)