二维数组中的查找

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

例如下面的二位数组就是每行每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数组5，由于数组不含有该数字，则返回false。
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15

分析

---

在分析这个问题的时候，很多应聘者会把二维数组画成矩形，从数组中选取一个数字，分3种情况来分析查找的过程，当数组中选取的数字刚好和要查找的数字相等时，就结束查找过程，如果选取的数字小于要查找的数字，那么根据排序的规则，要查找的数字应该在当前选取的位置的右边或者下边。

那么问题来了

---

由于要查找的数字相对于当前选取的位置有可能在两个区域中出现，而且这两个区域还有重叠，问题看起来就复杂了。

换一种分析方法

---

这里分析一个复杂的问题时，一个很有效的办法就是从一个具体问题入手，通过简单的分析，找出规律。
** 前面我们之所以遇到问题，是因为我们在二维数组的中间选取一个数字来和要查找的数字做比较，这样导致下一次要查找的是两个相互重叠的区域。如果我们从数组的一个角上选取数字来和要查找的数字做比较，情况会不会好一点？ **
首先我们选取数组右上角的数字9，因为7<9，9的纵向一列都大于9，所以9所在的一列都一定比7大，这样就可以把这列从数组中去掉。接下来到了8，8<9，继续去掉8所在的一列，到了2，2>7，此时2所在的行中，2是最大的，最大的还小于7，所以这行所有元素均小于7，所以去掉2所在的这样，到了4，4也小于7，同理，去掉4所在的一行。最终找到了7.

总结规律

---

那么规律貌似可以总结出来了，我们每次要查找一个数字b，可以从二维数组中的右上角的数a查找，如果a<b，则去掉a所在的行，如果a>b，则去掉a所在的列。就这样一直查找，直到数组中没有元素为止。

实现代码如下

bool Find(int *martix,int rows,int column,int number) { bool flag = false; int row=0; int col=column-1; if(martix!=NULL&&rows>0&&column>0) { while (row<rows&&col>=0) { if(martix[row*column+col]==number) { flag = true; break; } else if (martix[row*column+col]>number) col--; else if (martix[row*column+col]<number) row--; } } return flag; }