我想出了剑指offer书上没有的解法！

作者 | 梁唐

大家好，我是梁唐。

最近又重刷了剑指offer，发现其中一些题目很有意思。于是拿出来写成文章和大家分享。

今天我们来看下剑指offer第三题，二维数组查找元素。

题意

题目的描述很简单，给定一个二维数组，保证这个数组的每行和每列都是递增的。再给定一个数target，要求返回一个bool值，表示target是否在数组当中。

本题在LeetCode当中也有，是LeetCode第74题。

书中给定的样例是下面这个矩阵，target是7。

强行二分

对于样例，我们一眼就看出来7在数组当中，但是如果要用程序来实现，应该怎么做呢？

比较容易想到的是，可以利用数组当中的行和列的有序性。比如，我们可以忽略列，逐行进行二分搜索。如果每一行都找不到target，就说明target不存在，否则说明target存在。

对于一个n x m的矩阵来说，每一行进行二分的复杂度是

，我们要找n行，所以整体的复杂度是

。这个复杂度肯定是可以接受的，毕竟二维矩阵的空间复杂度更大。n和m如果过大，内存会首先扛不住。

显然，这个方法还有优化的空间，因为我们没有用上每一列也是有序的这个条件。那怎么才能用上呢？

比较容易想到的是可以二分，但是再继续往下一想，会发现这题并没有那么简单。我们假设某一次二分的位置是(x, y)，接着我们要做的就是对比matrix[x][y]和target的大小关系。

这一对比问题就浮现了，如果matrix[x][y] < target，那么target可能出现的位置有哪些呢？我们来简单作一张图。

假设下图中间交叉的位置是(x, y)，很容易可以确定，右下角的阴影部分是可能的。因为它当中的每一个元素的行和列都大于matrix[x][y]，根据矩阵的性质，右下角的每一个元素都大于等于matrix[x][y]。

其次我们会发现，除了右下角，还有两个地方的元素也有可能满足条件，也就是下图当中橙色标记的部分：

虽然这两个区域只有一个横坐标或者纵坐标大于(x, y)，但其中的元素一样有可能大于matrix[x][y]。也就是说在这种情况下，我们只能舍弃掉一个部分。

对于matrix[x][y] > target的情况，也相似，四个部分只能舍弃掉一个。

当然，我们可以将矩形分成四个部分，舍弃掉一个之后，对于三个部分进行递归。但显然，这样非常麻烦，不仅代码难写，而且也很难调试。

缩小范围

直接套二分是不行的，我们需要对问题进行深入地分析。

很容易发现，对于这样的二维数组而言，左上角的元素一定是最小的，右下角的元素一定是最大的。而右上角和左下角的元素波动性很大，很小或很大都有可能。这看似是一个难点，我们无法确定矩阵当中元素的大小关系，但其实也是一个突破口。

以右上角为例，我们仔细观察就会发现，这个位置的元素的性质非常特殊。为了方便书写，我们假设右上角的元素是k，根据矩阵的定义: k = matrix[0][m-1]。

如果k < target，说明了什么？说明了我们可以直接排除掉第0行，因为k已经是第0行最大的元素了。如果k > target呢？我们则可以排除掉最后一列，因为k是这一列最小的元素。

所以，只要我们利用这个性质，逐行或者逐列地缩小范围，就可以一直向target逼近。

把这个思路想明白了，代码其实非常简单，只有一重while循环：

int findNumberIn2DArray(const vector<vector<int>> &mat, int target) {
    int n = mat.size();
    int m = mat[0].size();

    int x = 0, y = m-1;
    while (true) {
        if (x >= n || y < 0) {
            return 0;
        }
        if (mat[x][y] == target) {
            return 1;
        }
        // 如果大于target，舍弃一列
        if (mat[x][y] > target) {
            y--;
        }
        // 如果小于target，舍弃一行
        if (mat[x][y] < target) {
            x++;
        }
    }
}

由于我们每次都能舍弃一行或者一列，最多只能执行n+m次，所以这是一个

的算法。对于这道题来说，已经足够快了。

再次二分

到这里看似已经完美了，但如果我们仔细思考，还是能找到一点怪异的地方。既然右上角有这么好的性质可以用来缩小范围， 我们为什么一定要一行或者一列地缩小呢，就没有什么快速一点的办法么？

当然是有的，别忘了，这个矩阵的每行和每列都是有序的。所以我们可以通过二分来缩小范围。

具体的做法也非常简单，我们轮流缩小右上角的行和列，直到找到target或者抵达边界为止。比如我们先对第0行做二分，找到大于等于target的第一个元素。假设二分之后的位置是(0, k)，那么显然，对于k+1以及右侧的每一列即下图中红色部分都可以舍弃了，因为其中的所有元素都大于target。

同理，我们接着对第k列做二分，找到大于等于target的第一个元素，我们假设这个位置是l，那么对于l以上的每一行都可以舍弃不看了，即下图蓝色部分。

我们就这样行和列交替二分，一样可以迅速缩小范围，并且缩小的速度要比逐行和逐列更快。

附上代码：

int findNumberIn2DArray(const vector<vector<int>> &mat, int target) {
    int n = mat.size();
    int m = mat[0].size();

    int x = 0, y = m-1;
 // 标记当前是行二分还是列二分
    int mark = 0;
    while (true) {
        if (mark == 0) {
            // 行二分可以直接调用lower_bound，返回大于等于target的第一个位置
            int pos = lower_bound(mat[x].begin(), mat[x].begin() + y + 1, target) - mat[x].begin();
            if (pos < m && mat[x][pos] == target) return 1;
            if (pos == 0) return 0;
            // 因为pos的位置大于target，所以要-1
            y = pos - 1;
        }else {
            // 列二分需要手动做
            int l = x, r = n-1;
            while (l <= r) {
                int _m = (l + r) >> 1;
                if (mat[_m][y] == target) return 1;
                else if (mat[_m][y] < target) {
                    l = _m + 1;
                }else {
                    r = _m - 1;
                }
            }
            if (l >= n) return 0;
            x = l;
        }
        mark = 1 - mark;
    }
}

由于交替做二分，所以代码会稍稍复杂一些。有一些细节需要注意一下，比如我们按行进行二分的时候，在做列二分之前需要将位置减一。因为我们找到的是大于（等于的情况排除了）target的位置，整个一列的元素也都会大于target。

为什么做列二分的时候没有像这样调整呢？因为在做列二分的时候，我们本身就是要停在一个大于（等于的情况会触发return）target的位置，所以不需要再调整。

这些细节说实话如果不是对其中的位置以及二分的各种情况梳理得很清楚是很容易引起混乱的，经常会出现逻辑已经想明白了，但是调试的时候就是有问题的尴尬情况发生。所以我还是强烈推荐，大家都试着使用这样的算法实现一下代码，体会一下其中的细节。

最后，多说一句，剑指offer书上只有第二种解法，也就是逐行逐列缩小范围的解法，并没有最后一种二分的方法。我翻了几个大佬的题解，也都没看到二分的解法。虽然肯定不是第一个想出来的，不算原创也算是我独立思考得到的。当然，能想到这个解法也不是什么了不起的事，毕竟每行每列都有序的指向性太强了。

其实我们刷题除了提升算法的熟练度和代码的编码能力之外，很大一部分也是训练我们对于指向性的敏感程度。能够从题意或者是一些细节当中捕捉到关键信息，联想到一些算法和解法，从而找到突破口把题目做出来。相比这些，题目的数量和难度其实都不是最关键的。

希望大家都能好好刷题，多多思考，沉淀出一些属于自己的东西。