在排序的二维矩阵中搜索

Question

M是一个整数2D矩阵（nXm），它们按行和列进行排序。编写一个函数search(int s)，返回数字的确切位置或Null。最有效的方法是什么？

- user399950

---

准备面试... - user399950

那么我们确定矩阵中这个数字最多只出现一次吗？ - sandris

我们知道每个数字只出现一次吗？问题说明它想要数字的确切位置，如果有多个位置，我们返回第一个找到的位置吗？ - Jack

Answer 1

初始化: m[1..n(行),1....m(列)]

i=n，j=1

从(i,j)开始：

STEP 1) if the value equals m(i,j) return (i,j)
STEP 2) if the value > m(i,j) go to step 1 with j+=1
STEP 3) else go to step 1 with i-=1

在每一步中，如果 j 或 i 超出范围，则返回无解。

这个解决方案的复杂度是 O(n+m)，如果 n=m，则复杂度为 O(n)。

我想知道是否有像二分查找那样的 log(n*m) 解决方案。

编辑 另一个可能的解决方案：

STEP 1)take the middle (n/2,m/2) of the matrix and compare it to the value
STEP 2) if the value equals m(i,j) return (i,j)
STEP 3) if the value is higher you can get rid from the first quarter  
STEP 4) if the value is lower you can get rid from the forth quarter
STEP 5) split the 3 other quarters to 2, a rectangle and a box, 
        send those both items to step 1 in a recursive manner

我不确定这种解决方案的效率： 如果 R = N*M，则 T(R) = T(R/2) + T(R/4) + O(1)

（如果R等于N乘以M，那么T(R)等于T(R/2)加上T(R/4)再加上O(1)）

- DuduAlul

---

一位教授给了我这个有趣的问题；我很快就想出了你的递归分治算法（在正方形上递归，并设置T(R) = 3T(R/4)，根据主定理，时间复杂度为O(R^(log_{4}(3))) = O(R^0.8)），但是无法想出O(n+m)的算法。当我最终放弃时，他说“走相反的对角线”，我立刻恍然大悟！ - BlueRaja - Danny Pflughoeft

Answer 2

假设我们有以下代码：

1 2 5 7
2 4 7 9
3 5 8 9
5 6 9 9

现在我们要搜索数字6。您可以看到从右上角（5 7）到左下角（5 6 7）有一条“条纹”，其中小于6的值翻转为大于6的值（用*标记的“条纹”）：

1 2 5*7
2 4*7 9
3 5*8 9
5*6*9 9

所以一个算法会是：

• 检查左上角是否比您的数字大 -> 返回 null
• 检查右下角是否比您的数字小 -> 返回 null
• 沿着从左上到右下的对角线走，直到找到“条纹”
• 在两个方向上跟随条纹，直到找到数字。

- Landei

---

我更倾向于说它是O(sqrt(n))。首先，当我们谈论排序一堆数字时，n显然是数字的数量（而不是正方形的边长）。在最坏情况下，找到条带需要sqrt(n)的时间，而条带本身的最大长度为2 * sqrt(n)。当然，如果数组不是正方形而是一个平面矩形，则该方法会变得更糟。 - Landei

所以我猜这不是最有效的算法，因为我可以只迭代矩阵....一定有更好的解决方案，不是吗？ - user399950

这肯定比遍历矩阵要好，但是在KennyTM指出的链接中有一些聪明的解决方案，可能会更好。 - Landei

它具有与任何其他可能算法相同的最坏情况复杂度。使用分治法，我们可以改善典型和最佳情况。 - mdma

Answer 3

考虑以下输入：

1 2 3

4 5 6

7 8 9

例如，DuduAlul的算法将无法找到数字4的位置。

- GA1

Answer 4

我刚刚打开记事本写了一点，但我认为这将在O(x)时间内完成，其中x是n和m之间较大的索引。该算法的最坏情况是搜索项等于数组中最大的项，对于这种情况，该方法将循环n或m（较大者）次。如果这种情况经常发生，可以从右下角开始而不是左上角，并递减索引而不是递增它们。

int[] SearchArray(int s, int[][] array)
{
    int i = 0;
    int j = 0;
    int n = array.GetLength(0);
    int m = array.GetLength(1);
    if (s > array[n][m])
            return null;
    while (i < n && j < m)
    {
        if (array[i][j] > s)
            return null;
        if (array[i][j] == s)
            return new int[]{i,j};
        try
        {
            if (array[i+1][j+1] < s)
            {
                    i++;
                    j++;
            }
            else if (array[i+1][j] > array[i][j+1])
                if (array[i+1][j] < s)
                    i++;
                else
                    j++;
            else if (array[i][j+1] > array[i+1][j])
                if (array[i][j+1] < s)
                    j++;
                else
                    i++;
            else if (array[i+1][j] == array[i][j+1])
                if (n < m)
                    i++;
                else
                    j++;
        }
        catch(IndexOutOfRangeException e)
        {
            if (i == n-1)
                j++;
            if (k == m-1)
                i++;
        }
    }
}

---

为了优化和格式化而编辑

- T.K.