我在 O(n) 时间内查看一个值是否在二维数组中的方法有什么问题？

Question

我正在尝试编写一个采用二维数组的方法（排列方式是每行中的元素从左到右递增，每列中的元素从上到下递增) 和一个 int，然后查看 int 是否在二维数组中。我想使用嵌套循环，但这会使它在 O(N^2) 时间内完成。因此，我正在尝试制作条件语句，以便它测试 int 是否小于子数组中的第一个并且大于最后一个，如果是，则进入下一个子数组。这是我拥有的：

 static boolean has(int number, int[][] a) {
    int q = 0;
    boolean c = false;

    for (int i = 0; i < a[q].length-1; i++){
      if ((number < a[i][q]) || (number > a[a[j].length-1][i])){
        q++;
      }
      else if (number == a[i][q]){
        c = true;
        break;
      }
      else c = false;
    }
    return c;
  }

需要一些帮助。此方法编译但给了我 outOfBounds 谢谢！

Answer 1

此解决方案的运行时间复杂度为 O(n+m)：

static boolean has(int number, int[][] a) {
    int row = 0;
    int col = a[0].length - 1;
    while (row < a.length && col >= 0) {
        int n = a[row][col];
        if (n < number) {
            row++;
        } else if (n > number) {
            col--;
        } else {
            return true;
        }
    }
    return false;
}

Answer 2

您可以在 O(log(n) + log(m)) 中解决此问题，首先使用二进制搜索找到包含您要查找的整数的行（因为列已排序），然后找到确切位置该行中的整数，通过执行另一个二进制搜索（因为行已排序）。

我在 O(n) 时间内查看一个值是否在二维数组中的方法有什么问题？

What is wrong with my method to see if a value is in a 2D array in O(n) time?

java

big-o

multidimensional-array