java - 在二维排序数组中搜索元素

Question

我必须编写一个代码(作为练习)来接收一个 2D(方形)按行和按列排序的数组和一个元素，如果该元素存在于数组中，则返回 true。

当我听到“排序”时，我首先想到的是二分搜索，但后来我意识到每行中的最后一个元素不一定小于下一行中的第一个元素。

所以，我发现最好的复杂度是 O(n)，并编写了以下代码:

 public static boolean findN(int[][] a, int x) {
    if (a.length == 0 || a[0].length == 0 || x > a[a.length - 1][a[0].length - 1] || x < a[0][0]) {
        return false;
    }
    int LastRow = a.length - 1, Lastcol = a[0].length - 1, row = 0, col = 0;

    while (row <= LastRow) {
        if (a[row][col] == x) {
            return true;
        } else if (col < Lastcol) {
            col++;
        } else {
            col = 0;
            row++;
        }
    }
    return false;
}

array example:

int [] [] arr = {{1,2,7,30}
                        {2,4,18,50}
                        {3,6,19,90}
                        {4,7,20,91}}

• 在意识到最佳复杂度为 O(n) 后，我用 google 搜索了这个问题所以我几乎可以肯定我是对的(尽管有些人声称他们可以在 O(log(n))) 中完成，但我真的吗？
• 欢迎任何其他想法和改进，提前谢谢大家!

Answer 1

几个月前我遇到了类似的问题，这是我发现在 O(logN + logM) 中工作的代码[假设数组按行和按列排序]。

[...] 但我意识到每行中的最后一个元素不一定小于下一行中的第一个元素。 - 在这种情况下，您无法实现 O( logn)复杂性。

简单的二分查找:

static void binarySearch(int mat[][], int i, int j_low, int j_high, int x) { 
    while (j_low <= j_high) { 
        int j_mid = (j_low + j_high) / 2; 

        // Element found 
        if (mat[i][j_mid] == x) { 
            System.out.println ( "Found at (" + i  + ", " + j_mid +")"); 
            return; 
        } 

        else if (mat[i][j_mid] > x) 
            j_high = j_mid - 1; 

        else
            j_low = j_mid + 1; 
    } 

    System.out.println ( "Element no found"); 
} 

核心逻辑:

static void sortedMatrixSearch(int mat[][], int n, int m, int x) { 
    // Single row matrix 
    if (n == 1) { 
        binarySearch(mat, 0, 0, m - 1, x); 
        return; 
    } 

    // Do binary search in middle column. 
    // Condition to terminate the loop when the 
    // 2 desired rows are found 
    int i_low = 0; 
    int i_high = n - 1; 
    int j_mid = m / 2; 
    while ((i_low + 1) < i_high) { 
        int i_mid = (i_low + i_high) / 2; 

        // element found 
        if (mat[i_mid][j_mid] == x) { 
            System.out.println ( "Found at (" + i_mid +", " + j_mid +")"); 
            return; 
        } 

        else if (mat[i_mid][j_mid] > x) 
            i_high = i_mid; 

        else
            i_low = i_mid; 
    } 

    // If element is present on  
    // the mid of the two rows 
    if (mat[i_low][j_mid] == x) 
        System.out.println ( "Found at (" + i_low + "," + j_mid +")"); 
    else if (mat[i_low + 1][j_mid] == x) 
        System.out.println ( "Found at (" + (i_low + 1)  + ", " + j_mid +")"); 

    // Ssearch element on 1st half of 1st row 
    else if (x <= mat[i_low][j_mid - 1]) 
        binarySearch(mat, i_low, 0, j_mid - 1, x); 

    // Search element on 2nd half of 1st row 
    else if (x >= mat[i_low][j_mid + 1] && x <= mat[i_low][m - 1]) 
    binarySearch(mat, i_low, j_mid + 1, m - 1, x); 

    // Search element on 1st half of 2nd row 
    else if (x <= mat[i_low + 1][j_mid - 1]) 
        binarySearch(mat, i_low + 1, 0, j_mid - 1, x); 

    // search element on 2nd half of 2nd row 
    else
        binarySearch(mat, i_low + 1, j_mid + 1, m - 1, x); 
} 

驱动方法:

public static void main (String[] args) { 
    int n = 4, m = 5, x = 8; 
    int mat[][] = {{0, 6, 8, 9, 11}, 
                   {20, 22, 28, 29, 31}, 
                   {36, 38, 50, 61, 63}, 
                   {64, 66, 100, 122, 128}}; 

    sortedMatrixSearch(mat, n, m, x); 
} 

希望这有帮助。祝你好运。