search - 在排序矩阵(mXn)中查找特定值，时间复杂度为 O(lgm) + O(lgn)

Question

矩阵 A 按行和列排序，其中 A[i][j] < A[i][j+1] 且 A[i][j] < A[i+1][j]。附加信息是每行的第一个元素小于前一行的最后一个元素，例如:

⎡1  3   5  17⎤
⎢2  4   6  18⎥
⎣7  9  11  20⎦

我很困惑这些附加信息在确定 O(lgn) 复杂度方面起什么作用。

我可以得出 O(m) + O(n) 如下:

int search(int mat[4][4], int n, int x)
{
   int i = 0, j = n-1;  //set indexes for top right element
   while ( i < n && j >= 0 )
   {
       if ( mat[i][j] == x )
       {
          printf("\n Found at %d, %d", i, j);
          return 1;
       }
       if ( mat[i][j] > x )
           j--;
       else //  if mat[i][j] < x
           i++;
       }

       printf("\n Element not found");
       return 0;  // if ( i==n || j== -1 )
  }

但我认为我没有使用该信息:每行的第一个元素小于前一行的最后一个元素

有人可以给我一些提示吗？另外，这不是家庭作业。谢谢!

Answer 1

您当前正在做的是详尽的搜索(即检查每个元素一次)，因此 O(n*m)。您没有利用矩阵的排序性质。

给定一个排序列表，Binary Search让您在 O(lg n) 内进行搜索。基本上，您检查列表的中间元素。如果它大于您的目标，那么您知道您可以忽略列表的后半部分。重复此过程，每次将搜索空间减半，直到找到该元素或搜索空间等于 1 项。在Python代码中:

import math

def binSearch(value, data):
    bottom = 0 #first entry
    top = len(data) -1 #last entry

    while bottom <= top: #if bottom ever becomes greater than top then the object is not in the list
        i = int(bottom + math.floor((top - bottom)/2)) #find the mid-point
        if data[i] == value: #we found it
            return i
        elif data[i] > value:
            top = i - 1 #value must be before i
        else:
            bottom = i + 1 #value must be after i

    return None #not found

现在，考虑一下您可以从矩阵结构中收集哪些信息。你知道给定一个 n x m 矩阵 mat按照您的描述排序，对于任何行 i , mat[i][0]是行中最低的项目，mat[i][n]是最高的。类似地，对于任何列 j，mat[0][j]是该列的最小值，mat[m][j]是最高的。这意味着如果 mat[i][0] <= value <= mat[i][n]不成立则值不能位于第 i 行。类似地，如果 mat[0][j] <= value <= mat[m][j]不正确则值不能位于 j 列中。

因此，明显的改进是，对于可能包含该值的每一行，进行二分搜索。

for row in mat:
    if (row[0] <= value) AND (row[len(row) - 1] >= value): #if the value could possibly be in the row
        result = binSearch(value, row)

        if result: #if we found it
            return result

binSearch()是 O(lg·m)。最坏的情况是执行 binSearch()在每一行上，因此 O(n * lg m)。

我试图实现一个 O(lg n * lg m) 解决方案，但我无法弄清楚。问题是我只能消除矩阵的左上角和右下角。我无法消除左下角或右上角。