【解题】二维数组中的查找（C++实现）

54 阅读 0 评论 36 点赞

我是靠谱客的博主激昂百合，最近开发中收集的这篇文章主要介绍【解题】二维数组中的查找（C++实现），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：在一个二维数组中，每一行按照从左至右递增的顺序排列，每一列按照从上至下递增的顺序排列。输入一个数字，判断数组中是否存在该数字。

一、分析
对于这个问题，一种很简单粗暴的方法就是全部循环一遍，就能判断给定数字是否在二维数组中。但是这样的话，给定的每行、每列按序递增的条件岂不是多余了吗？而且，当二维数组相当庞大并且需要查找的数字要刚好比较靠后的时候，全部循环的时间代价是很高的。

在前面的一维数组查找中，笔者和大家简单的探讨了分治思想的实际应用，那里使用的具体方法可以称之为二分查找法。那么，在二维数组的查找中能不能利用类似的思想呢？

笔者认为这是可行的，我们可以利用给定的数组特点（即每行、每列按序递增）以及采取相应的方法来缩小每一次需要查找的范围。在一维数组的二分查找中，我们是通过选取数组的中点值来与待查找值做比较从而一步步缩小查找范围。那么关键问题就变成了：我们如何来选取一个合适的参考点（参考值）呢？

二、算法描述
如何来回答上述问题呢？一个有效的方法就是通过实际的例子入手，通过一步步的分析试图找出普遍的规律。

1、类似于二分查找，选取二维数组中间的数值：这种思路是根据一维数组的实践经验很快速的就能想到的。但是我们继续思考，会发现：当选取数组中间的那个数值且待查找数值不是它的时候，待查找数值的分布区域将会有重叠（如下图1）。这样我们会感觉到无法继续，于是只好换一种思路。

这里写图片描述
（图1：红色表示选取的参考点，假设待查找数值大于参考点，那么待查找数值将分布在图中的阴影部分）

2、选取角落作为参考点：比如我们选取右上角的值作为参考点。（建议仿照上图1画图理解）

当待查找数值小于参考点的时候，待查找数值不会在参考点的右边或者下边，那么便可以剔除参考点所在的那一列，从而缩小查找范围。
当待查找数值大于参考点的时候，那么带查找数值不会出现在参考点的左边和上边，那么便可以剔除参考点所在那一行。

概括一下，便可总结出算法描述：首先选取数组的右上角数值，若该数值等于要查找的数值，则结束并返回true；如果该数值大于要查找的数值，剔除这个数值所在的列；如果该数值小于要查找的数值，剔除这个数值所在的行；

三、代码实现：

/*
matrix:用一维数组来模拟二维数组存储
rows：二维数组的总行数
cols：二维数组的总列数
number：要查找的数值
*/
bool find(int *matrix, int rows, int cols, int number)
{
    bool found = false;
    if (matrix == NULL || rows <= 0 || cols <= 0)
        return false;

    int row = 0;
    int col = cols - 1;
    while (row < rows&&col >= 0)
    {
        if (matrix[row*cols + col] == number)   //选取右上角的数字
        {
            found = true;
            break;
        }
        else if (matrix[row*cols + col]>number)
            --col;     //剔除所在列
        else
            ++row;     //剔除所在行

    }
    return found;
}