转载请注明出处：http://blog.csdn.net/ns_code/article/details/24977113
剑指offer上的第三道题目，在九度OJ上测试通过
题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入：输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为两个整数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 秒
内存限制：32 兆
采用二分查找法，时间复杂度为O(max(m,n))。先将给定的值key与二维数组右上角的元素比较，若相等，则返回true，若key小于它，则最后一列的元素肯定都大于key，此时可以删除掉最后一列，而若key大于它，则第一行的元素肯定都小于key，此时可以删除掉第一行，依次向下比较，如果比较到了左下角的元素，还没有发现等于key的，则返回fasle。
实现代码如下：
[cpp] view plain copy #include<stdio.h> #include<stdbool.h> /* 在m*n的升序二维数组matrix中查找是否有key */ bool Find(int *matrix,int m,int n,int key) { if(matrix==NULL || m<1 || n<1) return false; int row = 0; int col = n-1; while(row<=m-1 && col>=0) { if(matrix[row*n+col] == key) return true; else if(matrix[row*n+col] > key) col--; else row++; } return false; } int main() { int m,n; while(scanf("%d %d",&m,&n) != EOF) { int key,i; //不加static会产生栈内存溢出， //如果不加static，matrix数组的内存在栈内分配， //如果加static，matrix数组的内存分配在全局已初始化区。 //另外，此处用最大范围的数组，会增大所用内存， //但如果用malloc动态分配，则会增加运行时间。 static int matrix[1000*1000] = {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\n"); else printf("No\n"); } return 0; } /************************************************************** Problem: 1384 User: mmc_maodun Language: C Result: Accepted Time:680 ms Memory:4820 kb ****************************************************************/
