题目：二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解析

可以肯定的是直接遍历不可取🙄。之后想到跳步判断，先走斜线，若此时数值大于查找数则往左或往右倒退？往左之后该往上还是往下？继而联想到A*路径查找算法……
naive ! 书中指出考虑每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。问题变得困难是因为考虑数组中中间位置的数，此时该位置含有两个排序规律；不如考虑特殊位置-顶角的数呢？
二维数组有四个顶角，选择其中某个顶角分析。举例分析：
有如下二维数组，查找数字 7
$$
\begin{bmatrix}
1 & 2 & 8 & 9 \\
2 & 4 & 9 & 12 \\
4 & 7 & 10 & 13 \\
6 & 8 & 11 & 15 \\
\end{bmatrix}
$$
对四个顶点分情况讨论(↓、→、↘表示增大方向)：

考虑左上角则有规律：对于左上角有三个出度
$$
\begin{bmatrix}
● & \rightarrow & \rightarrow & \rightarrow \\
\downarrow & \searrow & \downarrow & \downarrow \\
\downarrow & \rightarrow & \searrow & \downarrow \\
\downarrow & \rightarrow & \rightarrow & \searrow \\
\end{bmatrix}
$$
考虑右下角则有规律：对于右下角有三个入度
$$
\begin{bmatrix}
＋ & \rightarrow & \rightarrow & \rightarrow \\
\downarrow & \searrow & \downarrow & \downarrow \\
\downarrow & \rightarrow & \searrow & \downarrow \\
\downarrow & \rightarrow & \rightarrow & ● \\
\end{bmatrix}
$$
考虑右上角则有规律：对于右上角有一个入度和一个出度
$$
\begin{bmatrix}
＋ & \rightarrow & \rightarrow & ● \\
\downarrow & \searrow & \downarrow & \downarrow \\
\downarrow & \rightarrow & \searrow & \downarrow \\
\downarrow & \rightarrow & \rightarrow & \searrow \\
\end{bmatrix}
$$
考虑左下角则有规律：对于左下角有一个入度和一个出度
$$
\begin{bmatrix}
＋ & \rightarrow & \rightarrow & \rightarrow \\
\downarrow & \searrow & \downarrow & \downarrow \\
\downarrow & \rightarrow & \searrow & \downarrow \\
● & \rightarrow & \rightarrow & \searrow \\
\end{bmatrix}
$$

“柿子要捡软的捏”，当然选一出一入的突破口啊！例如选择右上角数字 9，则 9 > 7 说明第四列均大于 7，故判断数组范围缩小为
$$
\begin{bmatrix}
1 & 2 & 8 \\
2 & 4 & 9 \\
4 & 7 & 10 \\
6 & 8 & 11 \\
\end{bmatrix}
$$
继续选择右上角数字 8，则 8 > 7 说明第四列均大于 8，故判断数组范围又缩小
$$
\begin{bmatrix}
1 & 2 \\
2 & 4 \\
4 & 7 \\
6 & 8 \\
\end{bmatrix}
$$
继续选择右上角数字 2，则 2 < 7 说明第一行均小于 8，故判断数组范围双缩小
$$
\begin{bmatrix}
2 & 4 \\
4 & 7 \\
6 & 8 \\
\end{bmatrix}
$$
继续选择右上角数字 4，则 4 < 7 说明第一行均小于 8，故判断数组范围叒缩小
$$
\begin{bmatrix}
4 & 7 \\
6 & 8 \\
\end{bmatrix}
$$
选择右上角数字 7，则寻找完毕😄。转化为代码如下

bool findNumber(int *arr, int rows, int columns, int number)
{
    if (nullptr == arr || rows < 1 || columns < 1)
        return false;
    int row = 1;
    int column = columns;
    while (row <= rows && column > 1)
        if (arr + ((row - 1) + (column - 1) * rows) > number)
            --column;
        else if (arr + ((row - 1) + (column - 1) * rows) < number)
            ++row;
        else
            return true;
    return false;
}

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可