题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
误区
对于这道题，很多人从一般的角度思考解决方法：比如想到若数组检索对象大于该整数，则可以剔除该元素右下方的所有元素；若数组检索对象小于该整数，则可以剔除该元素左上方的所有元素。
可是然后呢？很多人就在这里卡住了。因为剔除后的区域遍历起来太过复杂，一时半刻谁也想不出来。
正解
应当从具体问题入手，通过分析简单具体的例子，发现普遍的规律。
现在假定，我们要从二维数组
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
中检索是否存在数字7。
按照从右上方，列优先的顺序检索该数组。
1. 在检索9的时候，因为7小于9，故可剔除第四列。
2. 在检索8的时候，因为7小于8，故可剔除第三列。
3. 在检索2的时候，因为2小于7，故可剔除第一行。
4. 在检索4的时候，因为4小于7，故可剔除第二行。
5. 检索到7，返回。
实现代码( 含测试 )
1 #include <iostream> 2 3 using namespace std; 4 5 const int M=4; 6 const int N=4; 7 8 /* 9 * 查找数字函数 10 */ 11 bool findNum(int a[M][N], int r, int c, int num) { 12 13 int sr =0; 14 for (int i=c-1; i>0; i--) { 15 for (int j=sr; j<r-1; j++) { 16 if (a[i][j] == num) 17 return 1; 18 else if (a[i][j] < num) { 19 sr++; // 剔除当前行 20 } 21 else { 22 break; // 剔除当前列 23 } 24 } 25 } 26 27 return 0; 28 } 29 30 int main(void) 31 { 32 /* 33 * 创建一个测试用的数组并打印 34 */ 35 int a[M][N] = { 36 {1, 2, 8, 9}, 37 {2, 4, 9, 12}, 38 {4, 7, 10,13}, 39 {6, 8, 11,15} 40 }; 41 42 cout << "要测试的数组："; 43 44 for (int i=0; i<M; i++) { 45 cout << endl; 46 for (int j=0; j<N; j++) { 47 if (a[i][j] >= 10) { 48 cout << a[i][j] << " "; 49 } 50 else 51 cout <<a[i][j] << " "; 52 } 53 } 54 55 // 测试函数是否运行正常 56 cout << endl << endl << "请输入要查找的数字:"; 57 int num; 58 while (cin >> num) { 59 if (findNum(a, M, N, num)) { 60 cout << "该数存在" << endl; 61 } 62 else { 63 cout << "该数不存在" << endl; 64 } 65 cout << endl << "请输入要查找的数字:"; 66 } 67 68 return 0; 69 }
小结
1. 一定要加强编程实践能力。
2. 别急着写代码，要做深刻的思考，有主体思路之后再写代码。
原文：http://www.cnblogs.com/scut-fm/p/3572398.html