《剑指offer》面试题3：二维数组中的查找

面试题3:二维数组中的查找

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

  例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返 false。

1	2	8	9
2	4	9	12
4	7	10	13
6	8	11	15

对于我们要找的数字，比如7，我们可以从右上角或者从左下角开始找。过程如下：

从右上角寻找：

如果 a[i][j] 比目标数大，则，向左侧寻找

9 > 7  —>   8 > 7
如果 a[i][j] 比目标数小，则，在下侧寻找
2 < 7  —>   4 < 7
如果 a[i][j] 等于目标数，则，查找成功
7 == 7
如果遍历完（行或列超出数组下标），没有该数

从左下角寻找：

如果 a[i][j] 比目标数大，则，向上侧寻找
如果 a[i][j] 比目标数小，则，在右侧寻找
如果遍历完（行或列超出数组下标），没有该数

//从右上角开始查找

bool Find(int *arr, int rows, int columns, int number)

{

	for (int i = 0, j = columns - 1; i > rows, j >= 0;)

	{

		if (arr[i * columns + j] == number)

		{

			cout << "arr" << '[' << i << ']' << '[' << j << ']' << '=' << number << endl;

			return true;

		}

		if (arr[i * columns + j] > number)	//a[i][j]

		{

			--j;

		}

		else if (arr[i * columns + j] < number)

		{

			++i;

		}

	}

	return false;

}

测试：

int main()

{

	int arr[4][4] = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };

	int flg = Find((int *)arr, sizeof(arr[0]) / sizeof(int), sizeof(arr) / sizeof(arr[0]),4);

	if (!flg)	cout << "查找失败" << endl;

}

测试结果：

《剑指offer》面试题3：二维数组中的查找的相关教程结束。