java - 数组搜索的时间复杂度

Question

我正在编写函数来检查给定值是否包含在 .该矩阵具有以下属性: • 每行中的整数从左到右按升序排序。 •每列中的整数从上到下按升序排序

public static boolean searchMatrix(int target, int[][] matrix)
{
    for(int i = 0;i <= matrix[0].length;i++)
    {
        for (int j=i; j<matrix.length;j++)
        {
        if(target == matrix[i][j])
        return true;
        }
    }
    return false;
}

我想知道这个程序的时间复杂度是否为 O(N)。 如果不是，我应该做什么改变才能进入 O(N)。

Answer 1

我认为搜索可以在线性时间内完成。将以下 4×4 矩阵视为视觉效果:

1 2 4 6
2 3 5 7      ascending from left to right
3 4 6 8      and from top to bottom
4 5 6 9

如果我们要搜索值5，我们可以从左上角开始，然后向右走，直到找到该值或遇到大于目标的数字5。在本例中，我们达到了 6。然后，我们可以回滚到 4，并前进到更高的行。确保第一行中的每个先前值都小于目标，并且从该列开始的下一行中的每个值都大于第一行上的值。

这是一种大致线性的方法。一个很好的类比是沿着山的周边行走，寻找某个高度。如果在每个点我们要么找不到我们想要的高度，要么只找到太高的点，我们就会继续行走。