题目1384：二维数组中的查找
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：7318
解决：1418
- 题目描述：
-
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
- 输入：
-
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为两个整数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
代码（一）：
题解：
1、找到所在位置所在行，通过和每一行最后一个元素比较
2、找到列中元素位置
#include <stdio.h>
#include <string.h>
int A[1010][1010];
void print(int flag){
if(flag == 2)
printf("Yes\n");
else printf("No\n");
}
int main(int argc, char const *argv[])
{
int m, n, mark, pos, i, j, x, y;
while(~scanf("%d %d", &m, &n)){
mark = 0;
scanf("%d", &pos);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
scanf("%d", &A[i][j]);
for(x=1;x<=m;++x){
if(pos > A[x][n])
continue;
else break;
}
if(x>m) {print(mark); continue;}
for(y=1;y<=n;++y)
if(pos == A[x][y]){
mark = 2;
break;
}
print(mark);
}
return 0;
}
代码（二）、
题解：
1、二分查找第几行
2、二分查找第几列
#include <stdio.h>
#include <string.h>
int A[1010][1010];
void print(int flag){
if(flag == 2)
printf("Yes\n");
else printf("No\n");
}
int main(int argc, char const *argv[])
{
int m, n, mark, pos, i, j, x, y;
int mid, h, l;
while(~scanf("%d %d", &m, &n)){
mark = 0;
scanf("%d", &pos);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
scanf("%d", &A[i][j]);
h = m;
l = 1;
while(l<h){
mid = (l+h)/2;
if(pos > A[mid][n])
l = mid+1;
else h = mid;
}
x = l;
if(x>m) {print(mark); continue;}
h = n+1;
l = 1;
while(l<h){
mid = (l+h)/2;
if(pos == A[x][mid]) {mark = 2; break;}
if(pos > A[x][mid])
l = mid+1;
else h = mid;
}
print(mark);
}
return 0;
}
代码（三）、
题解：
1、将二维数组转化成一维数组，进行二分查找
2、开数组注意是否爆出空间
#include <stdio.h>
int A[1000000];
int main(int argc, char const *argv[])
{
int i, pos, mul, m, n, flag;
int h, l, mid;
while(~scanf("%d %d %d", &m, &n, &pos)){
mul = m*n;
for(i=0;i<mul;++i)
scanf("%d", &A[i]);
h = mul;
flag = l = 0;
while(l<h){
mid = (h+l)/2;
if(A[mid] == pos){flag = 1; break;}
if(A[mid] > pos) h = mid;
else l = mid + 1;
}
if(flag == 1) printf("Yes\n");
else printf("No\n");
}
return 0;
}
代码（四）、
题解：
1、通过输入元素进行判断是否为所查找元素
#include <stdio.h>
int main()
{
int i, pos, mul, m, n, flag, dd;
while(~scanf("%d %d %d", &m, &n, &pos)){
flag = 0;
mul = m*n;
for(i=0;i<mul;++i){
scanf("%d", &dd);
if(dd == pos) flag = 1;
}
if(flag == 1) printf("Yes\n");
else printf("No\n");
}
return 0;
}
#include <stdio.h>
char tmp[8000];
int main()
{
int i,j,n,m,t,f,s;
while(scanf("%d%d",&n,&m)!=EOF){
scanf("%d",&t);f=0;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%d",&s);
f|=s==t;
}
if(f){
while(i<n){
fgets(tmp,8000,stdin);i++;
}
break;
}
}
if(f)printf("Yes\n");
else printf("No\n");
}
return 0;
}