《剑指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;
}