【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