【C/C++练习题】二维数组中查找

《剑指Offer》面试题4

1 问题描述

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

2 分析

按照二维数组元素之间的规律，选择从右上角（或者左下角）的元素开始查找。如果查找值相比元素值大，排除左边数据（一行）
如果查找值相比元素值小，排除下方数据（一列）。这样在每次比较后，都可以缩小查找范围，直到最终找到目标元素。

另外，二维数组在内存上是连续存储的，可以通过数组首地址+偏移量的方式定位数组中的元素。

3 代码

      /*
      **面试题4：二维数组中的查找
      **题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按
      **照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个
      **整数，判断数组中是否含有该整数。
      */
      #include "iostream"
      using namespace std;
      //函数：查找指定数组
      //输入：matrix数组、rows行数、columns列数、number查找的数字
      bool Find(int* matrix, int rows, int columns, int number)
      {
     	if ((matrix == nullptr) || (rows <= 0) || (columns <=0))
      	{//判断无效参数
     		return false;
      	}
     	int row = 0;
     	int column = columns - 1;
     	while (row < rows && column >= 0)
      	{//在数组范围内查找
     		if (matrix[row*columns + column] == number)
      		{//查找到目标
     			return true;
      		}
     		else if (matrix[row*columns + column] < number)
      		{//向下继续查找
      			row++;
      		}
     		else
      		{//向左继续查找
      			column--;
      		}
      	}
     	return false;
      }
      void test01()
      {
         int matrix[][4] = {
          	{1, 2, 8, 9},
          	{2, 4, 9, 12},
          	{4, 7, 10, 13},
          	{6, 8, 11, 15}
          };
         bool ret = Find(&matrix[0][0], 4, 4, 4);
          cout << "result:" << ret << endl;
      }
      int main(int argc, char const *argv[])
      {
     	test01();
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/96624687