面试题： 二维数组中的查找
/*
题目： 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成
一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该数。
*/
ps:（其实前段时间我就做过这道题，今天看到了，觉得还是有点生，那就再来一次吧）
题目分析： 在分析这个问题的时候，我们首先要看，在一个二维数组中查找一个数字是否存在，那么很多人就觉得
简单了
，遍历二维数组与所需要查找的数字进行比较不就完了！ 不可否认的是你说的是可行的，可是问题在于，
面试官会觉得孩子你是不是心太急啊！ 我费尽周折给二维数组加上这几个规律，居然完全被你给忽视了！
所以
嘛，对题目的分析很重要，从左到右递增，从上到下递增， 其中必有玄妙啊！我们大概举出这么一个例子：
/*（符合题目规律的二维数组）
1 2 3 4
2 3 4 5
3 4 5 6
*/
发现规律了吧！ 是不是二维数组的左 / 右上角，左 / 右下角都比较特殊了，但是细心的你会发现，只有右上角和左下
角的数字才更具有特殊性，方便我们查找，我们以右上角为例，4左边的数字都比他小，而下边的数字都比他大,依次
进行分析，构造出算法！
算法选择： 在题目分析中我们都其实已经找到了规律，那么遍历二维数组O（N）的算法我们就不采用了，我们采用
的算法时间复杂度小于O（N）， 我们这样，我们一进入函数就比较 key（需要查找的整数）和右上角数字的大小，
@如果key==4,那么就结束，
@如果key大于4 ，我们就排除一行，大致如下：
/*（key>4）
1 2 3 4
2 3 4 5
3 4 5 6
*/
那么 5就变成了右上角，继续与key进行比较，以此类推！直到找到key或者找完也没找到key结束！
@如果key小于4，那就排除一列，大致如下：
/*（key<4）
1 2 3
2 3 4
3 4 5
那么 3就变成了右上角，继续与key进行比较，以此类推！知道找到key或者找完也没找到key结束！
代码实现：
#include<stdio.h>
#include<stdlib.h>
/* 注意二维数组的传参可以是 int (*arr)[4],但不能是int arr[][]; */
int Find(int arr[][4], int rows, int cols, int key)
{
if(arr != NULL && rows > 0 && cols > 0)
{
/* 注意这块为什么定义变量row和col，因为要用下标查找数，但是cols和rows
还要作为循环终止的判断条件，所以不能动，于是需要另外定义两个变量进行下
标访问！*/
int row = 0;
int col = cols - 1;
while(row < rows && col >= 0)
{
/* 接下来就是 = > < key 的三种情况的判断 */
if(arr[row][col] == key)
return 1;//找到就返回1；
else if(arr[row][col] > key)
col--;
else
row++;
}
}
return 0;//0 表示没有找到
}
int main()
{
int arr[3][4] = {1,2,3,4,2,3,4,5,3,4,5,6};
int key = 6;//要查找的整数；
int row = 3;//二维数组的行；
int col = 4;//二维数组的列；
printf("%d\n",Find(arr,row,col,key));
system("pause");
return 0;
}
#运行结果：
ps: 这个题的代码的实现还是比较简单实现的，前提是找到方法！
本题到此结束！
谢谢！
剑指offer 面试题（二维数组中的查找） （2）
原文：http://blog.csdn.net/bitboss/article/details/51345939
