二维数组中的查找

题目描述：

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

思路：设需要查找的数为key，先二分查找最后一列不小于key的数的位置pos，然后二分查找pos行。

 1 #include <stdio.h>
 2 int a[1001][1001];
 3 int n,m;
 4 int binary1(int l,int r,int key,int col)
 5 {
 6     int mid = (l+r)/2;
 7     if(l==r)return l;
 8     if(key<=a[mid][col]) return binary1(l, mid, key,col);
 9     else return binary1(mid+1,r,key,col);
10 }
11 int binary2(int l,int r,int key,int row)
12 {
13     if(l>r)return -1;
14     int mid = (l+r)/2;
15     if(a[row][mid]==key) return mid;
16     if(key<a[row][mid]) return binary2(l, mid-1, key,row);
17     else return binary2(mid+1,r,key,row);
18 }
19 int main(int argc, const char * argv[])
20 {
21     int i,j,key;
22     while(scanf("%d%d",&n,&m)!=EOF)
23     {
24         scanf("%d",&key);
25         for(i=0;i<n;i++)
26             for(j=0;j<m;j++)
27                 scanf("%d",&a[i][j]);
28         int row = binary1(0, n-1, key,m-1);
29         int pos = binary2(0, m-1, key,row);
30         if(pos>=0)printf("Yes
");
31         else printf("No
");
32     }
33 }