算法-二维数组中的查找

Myth丶恋晨 2022-06-10 01:06 233阅读 0赞

**问题：**  
在一个二维数组中，每一行元素都按照从左到右递增的顺序排序，每一列元素都按照从上到下递增的顺序排序。实现一个查找功能的函数，函数的输入为二维数组和一个整数，判断数组中是否含有该整数。  
**解题思路：**  
比如一个二维数组是这样：  
![这里写图片描述][SouthEast]  
要查找数组7在不在数组内，根据前人总结出来的规律，我们可以这样做：  
选择从数组的右上角的点开始比较，此时该值为9，9>7，同时9还是第四列最小的数字，那么这意味着，第四列都不可能找到7，于是我们可以直接删除第四列。  
![这里写图片描述][SouthEast 1]  
绿色代表所在的行或者列已经排查完了，红色代表当前值。此时值为8，显然和之前的结果一样。  
![这里写图片描述][SouthEast 2]  
然后我们比较2与7，2<7，同时2的位置是当前行内最大的数值，这意味着该行内不可能找到7，于是删除该行：  
![这里写图片描述][SouthEast 3]  
4与2的情况相同，直接删除该行：

![这里写图片描述][SouthEast 4]  
最后我们找到了7。

这个思路关键的地方在于右上角点的选取，因为这个点的值是所在列的最小值和所在行的最大值，这就意味着：  
**要查找的数值如果比右上角的值大，那么它将大于整个行；**  
**要查找的数值比如果右上角的值小，那么它将小于整个列。**  
如果相等的话，查找就结束了~~~

所以无论是哪一种情况，都可以让我们删除一个行或一个列，下一次要比较的那个值就是删除后的二维数组的右上角的值，总之永远在用右上角的值在比较。

这个一个最大一个最小的特性，除了右上角的点之外，左下角也是满足的。

**代码实现**

bool Find(int* matrix, int rows, int columns, int number)
    {
        bool found = false;
    
        if(matrix != NULL && rows > 0 && columns > 0)
        {
            int row = 0;
            int column = columns - 1;
            while(row < rows && column >=0)
            {
                if(matrix[row * columns + column] == number)
                {
                    found = true;
                    break;
                }
                else if(matrix[row * columns + column] > number)
                    -- column;
                else
                    ++ row;
            }
        }
    
        return found;
    }

在上面的代码中有一个地方需要注意一下，二维数组取值的方式用的是这样：`matrix[row * columns + column]`，这是因为我们把二维数组作为参数传递了，**参数传递时将二维数组的强制转换为一维指针**，这就相当于把二维数组按照行连起来，连接成一个一维数组，那么`matrix[row * columns + column]`不就是对应二维数组中的第row行，第column列的那个数么。注意row和column是从0开始的。

[SouthEast]: /images/20220610/0e8f5894eec94105a73cfe1523bb5ca1.png
[SouthEast 1]: /images/20220610/6b692e3f14894a9e8d7cd65c4116fe9b.png
[SouthEast 2]: /images/20220610/eab939e2f2444f41b29419e1c90118e7.png
[SouthEast 3]: /images/20220610/3eb58779c9114a978b5e3a8e6b7fd99e.png
[SouthEast 4]: /images/20220610/627c2fea453f4a3a874a433c2f9c242b.png