问题：在一个二维数组中，每行的元素从左到右是递增的，每列元素从上到下是递增的。写一个函数，查找一给定的元素是否在此数组中
输入：一个二维数组，和一个待查找的数
输出：待查找的数在数组中输出“YES",否则输出”NO"
原始思路：最简单思路就是暴力搜索，遍历一遍数组中的元素时间复杂度为O(n2)。但是这样就没有用问题的已知条件（从左到右、从上到下递增），因此不是个好的解法
改进1：从第一行开始找，找到待查元素大的，如果还没找到，接着从第二行开始找，直到找到或到最后一个元素为止（如图），但是如果带查找的元素在最后，还得遍历到最后，时间复杂度还是O(n2)
改进2：上来在随机在里面挑一个，如果正好逮住，那就结束了；如果比待查找的元素大，那么他的左边和上边；否则在右边和下边。如下图。这样下来可以减少一部分元素的比较。在寻找1时，会话费反而很多时间，并不是个好的解决办法。
改进3：看两个比较关键的两个点——左下角和右上角。以右上角为例（如下图）。如果右上角元素等于带查找元素，那就返回真；如果右上角元素大于待查找元素，那就删除右上角元素所在列；否则删除其所在行。依次进行下去。
举例说明：
参考代码一：
#include <stdio.h> int find_value(int a[][4], int value, int x, int y)//(x,y)表示右上角坐标 { if ((x >= 0) && (y < 4)) { if (a[x][y] == value) return 1; else if (a[x][y] > value) return find_value(a, value, x-1, y); else return find_value(a, value, x, y+1); } return 0; } int main() { int a[4][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; int val; printf("Enter your number:"); scanf("%d", &val); if(find_value(a, val, 3, 0)) printf("Yes, find it\n"); else printf("No, not find it\n"); return 0; }
这里注意几个技术细节问题（c语言）：
1.二维数组的定义——第二位长度必须指明
我们知道一位数组定义可以不指名元素总的个数，例如int a[] = {1, 2, 3}，编译器会自动赋值长度为3；对于字符char a[] = {'a', 'b', 'c'}，自动赋值为4,（因为字符数组末尾有个默认‘\0’字符）
二维数组的本质也是一维数组，其元素是数组。是数组的数组。但是初始化是第二位必须指明int a[][3]是可以的，但是int a[][]绝对不行的。究其这样设计的原因：int a[][3]={1,2,3,4,5}是定义一个每个元素含有3和整形变量的数组的数组。编译器会自动区分为{{1,2,3}，{4,5}}，但是如果第二维也给省略了，这样编译器也傻眼了，到底给每个数组赋多大值，是{{1,2,3}，{4,5,0}}，还是{{1,2,3，4}，{5，0，0,0}}还是其他......
2.向函数中传递二维数组
方法一：形参给出第二维大小
#include <stdio.h> void Find(int a[][3]) //此处必须指明第二维的大小 { int i, j; for(i=0; i<3; i++) for (j=0; j<3; j++) printf("%d\n", a[i][j]); } int main() { int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; Find(a); return 0; }
方法二：形参指明指向指针的 数组
#include <stdio.h> void Find(int (*a)[3]) { int i, j; for(i=0; i<3; i++) for (j=0; j<3; j++) printf("%d\n", a[i][j]); } int main() { int
a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
; Find(a); return 0; }
对于方法二：这里怎么理解int (*a)[3]? 做个类比：应该都知道int *a指指向整形变量的指针，等价于int (*a)[1]，[1]指明个数。那么int (*a)[3]就是指明了3个指针，a指向第一个。不能去掉（），因为*的优先级小于[],对于a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}，*a[2]指7。（a[2]指向第2个数组的指针，*取出第一个来）下面程序例证：
#include <stdio.h> void Find(int (*a)[3]) { int i, j; printf("%d\n", *a[2]); } int main() { int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; Find(a); return 0; }
执行结果是7
对于方法一有个问题：怎么知道二维数组第一维是多大？对于数组是没有函数得知数组的大小，即传给函数一个数组（数组名）不能得出数组的大小，可以利用sizeof函数得出。
3.sizeof
函数是用来得出一个对象或类型名的长度，单位是字节。返回类型为long unsigned int(c语言输出格式为%lu)
语法：sizeof(object) //对象
sizeof(type) //类型
例如：
#include <stdio.h> int main() { //bool aa; char a; int c; int *i; char *j; printf("int_c:%lu**type_int:%lu\n", sizeof(c), sizeof(int)); printf("char_a:%lu**type_char:%lu\n", sizeof(char), sizeof(char)); printf("int *i:%lu**%lu\n", sizeof(i), sizeof(int)); printf("char *j:%lu**%lu\n", sizeof(j), sizeof(int)); return 0; }
通过运行结果分析：
下面看一维数组：
#include <stdio.h> int main() { int array[] = {1, 2, 3}; printf("array:%lu ###*array:%lu ###array+0:%lu\n", sizeof(array), sizeof(*array), sizeof(array+0)); printf("size1:%lu\n", sizeof(array) / sizeof(*array)); printf("size2:%lu\n", sizeof(array) / sizeof(array[0])); return 0; }
运行结果：
下面看二位数组
#include <stdio.h> int main() { int array[][2] = {1, 2, 3, 4, 5}; printf("array:%lu ###*array:%lu ###array+0:%lu ##**array:%lu\n", sizeof(array), sizeof(*array), sizeof(array+0), sizeof(**array)); printf("size1:%lu\n", sizeof(array) / sizeof(*array)); printf("size2:%lu\n", sizeof(array) / sizeof(array[0])); return 0; }
执行结果：
现在回顾先写到程序，貌似不完全符合题意，题目是传入一个二维数组，但是现在能做的的必须是传入第二维的大小，可不可以直接往函数中直接传二位数组呢？
4.二维数组传给函数当一维数组用——利用下标转换成一维数组的下标
#include <stdio.h> void Find(int *a, int num) { int i = 0; for(; i< num; i++) printf("%d\n", a[i]); } int main() { int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; Find((int*)a, 9); return 0; }
*********************好了，修改下思路三***********************
参考代码二：
#include <stdio.h> int find_value(int *a, int val, int rows, int cols) //val是待查元素。rows是二维数组行数，cols是列数 { int row = 0; int col = cols-1; while(row < rows && col >= 0) { if (a[row * cols + col] == val) return 1; else if (a[row * cols + col] > val) col--; else row++; } return 0; } int main() { int a[][4] = {1, 2, 8, 9, 2, 4, 9, 12, 4, 7, 10, 13,6, 8, 11, 15}; int val; printf("Enter your number:"); scanf("%d", &val); if(find_value((int*)a, val, 4, 4)) printf("Yes, find it\n"); else printf("No, not find it\n"); return 0; }
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/04/21/3033284.html，如需转载请自行联系原作者
