二维数组中的查找

题目描述：

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

 

输入：

输入可能包含多个测试样例，对于每个测试案例，

输入的第一行为两个整数m和n(1<=m,n<=1000)：代表将要输入的矩阵的行数和列数。

输入的第二行包括一个整数t(1<=t<=1000000)：代表要查找的数字。

接下来的m行，每行有n个数，代表题目所给出的m行n列的矩阵(矩阵如题目描述所示，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

 

输出：

对应每个测试案例，

输出”Yes”代表在二维数组中找到了数字t。

输出”No”代表在二维数组中没有找到数字t。

 

 1 #include<stdio.h>
 2 #define MAX 100
 3 int find(int arr[MAX][MAX],int m,int n,int key)
 4 {
 5     int high,low,mid;
 6     if(key <arr[0][0] || key >arr[m-1][n-1])
 7         return 0;
 8     else
 9     {
10         high = m-1;
11         low  = 0;        
12         while(low <= high)
13         {        
14             mid = low + (high-low)/2;
15             if(arr[mid][n-1]==key)
16                 return 1;
17             else if(arr[mid][n-1] > key)
18                 high = mid-1;
19             else
20                 low = mid +1;
21         }    
22 
23         if (arr[mid][n-1] < key)
24             mid++;
25         int temp = mid;
26 
27         high = n-1;
28         low  = 0;
29         while(low <= high)
30         {        
31             mid = low + (high-low)/2;
32             if(arr[temp][mid]==key)
33                 return 1;
34             else if(arr[temp][mid] > key)
35                 high = mid-1;
36             else
37                 low = mid +1;
38         }    
39         return 0;
40     }
41  
42 }
43 void main()
44 {
45     int i,j,k=0;
46     int m,n;
47     int arry[MAX][MAX];
48     int result[MAX];
49     int value;
50     while (scanf("%d%d",&m,&n)!=EOF)
51     {
52         scanf("%d",&value);
53         for(i=0; i<m;i++)
54         for (j=0;j<n;j++)
55         scanf("%d",&arry[i][j]);
56         result[k] = find(arry,m,n,value); 
57         k++;           
58     }
59 
60     for (i=0;i<k;i++)
61     {
62         if (result[i]==1)
63         {
64             printf("Yes\n");
65         } 
66         else
67         {
68             printf("No\n");
69         }
70     }
71 }

二维数组中的查找,布布扣,bubuko.com

二维数组中的查找

原文：http://www.cnblogs.com/churi/p/3718885.html