按线性时间在按列排序的数组中搜索值

Question

如何在线性时间O(n)按列排序的数组中搜索值？

我需要编写一个函数，它接受按列排序的2d数组，如果指定的值在数组中，则返回true。

按列排序的数组示例

int[][] m = {
      {1, 2, 3},
      {4, 6, 5},
      {8, 10, 9}
    };

如何在线性时间O(n)内解决这个问题？

Answer 1

考虑到数组是按列排序的，我们可以访问所有列来查找目标元素。假设在最坏的情况下有N列，我们必须访问所有的列，我们必须在M行中搜索每个列的元素。

由于矩阵是按顺序排序的，所以我们可以在log(M)中进行搜索，从而导致N*log(M)最坏的情况时间复杂度。

但是如果你的意思是O(n)作为N个元素，那么我们应该考虑优化更多。