java - Java 中有序二维数组搜索的最佳时间复杂度

Question

因此，我有以下代码来搜索已排序的二维数组以查找目标数字，但我不确定这是否是最佳时间复杂度，就像 Big-Oh，我读到有一种方法可以在 O(N) 中完成，但我不确定我的算法是否足够高效。

public class Search2DArray {

public static int search(int[][] arrayA, int number, int target) {
    int i = 0;
    int j = number - 1;
    while (i < number && j >= 0) {
        if (arrayA[i][j] == target) {
            System.out.printf("\n Found at %d, %d", i, j);
            return 1;
        }
        if (arrayA[i][j] > target) {
            j--;
        } else {
            i++;
        }
    }

    System.out.printf("\n Element not found");
    return 0;
}

public static void main(String[] args) {
    int arrayA[][] = {{1, 2, 3, 4}, 
                   {5, 6, 7, 8}, 
                   {9, 10, 11, 12}};
    search(arrayA, 3, 11);
}
}

Answer 1

如果您的二维数组已排序，您可以简单地减少要选择的行，并对您认为包含目标数字的行运行二分搜索，这可能会降低复杂性，甚至可能会按 LOG 的顺序排列