二维数组中的查找概述

二维数组中的查找概述2015-09-22这一题给跪，c++死活超时。。。后来main函数改成用c就好了。。。

算法：

/* 题目描述： 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 输入： 输入可能包含多个测试样例，对于每个测试案例， 输入的第一行为两个整数m和n（1<=m,n<=1000）：代表将要输入的矩阵的行数和列数。 输入的第二行包括一个整数t（1<=t<=1000000）：代表要查找的数字。接下来的m行，每行有n个数，代表题目所给出的m行n列的矩阵（矩阵如题目描述所示，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 输出： 对应每个测试案例， 输出”Yes”代表在二维数组中找到了数字t。 输出”No”代表在二维数组中没有找到数字t。 样例输入： 3 3 5 1 2 3 4 5 6 7 8 9 3 3 1 2 3 4 5 6 7 8 9 10 3 3 12 2 3 4 5 6 7 8 9 10 样例输出： Yes No No ------------------------------------------------- 原理： 每次选取数组右上角的数字进行比较，若该数字比待查找数字大，那么删掉这一列；如果该数字比待查找数字小，那么删除这一行；这样一来，每次都可以使二维数组减少一行或一列，最终可以查找到该元素。 */#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;#define MAX 1000000bool Find（int arr[],int row,int column,int target）{int r,c;if（arr==NULL || row<1 || column<1）{return false;}r = 0,c = column-1;while（r<=row-1 && c>=0）{if（target == arr[r*column+c]）{return true;}else if（target > arr[r*column+c]）{r++;}else{c--;}}return false;}int main（）{int m,n;while（scanf（"%d %d",&m,&n） ！= EOF）{int key,i;static int matrix[MAX] = {0};scanf（"%d",&key）;for（i=0;i<m*n;i++）scanf（"%d",matrix+i）;bool result = Find（matrix,m,n,key）;if（result）printf（"Yes
"）;elseprintf（"No
"）;}return 0;}

作者：csdn博客 RowandJJ