| 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，诶一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否包含了该整数。 |
例如下面的二维数组就是每行、没列都递增排序。如果在这个数组中查找数字7，则返回true（找得到）；如果查找数字5，由于数组不含该数字，则返回false。
| 1 | 2 | 8 | 9 |
| 2 | 4 | 9 | 12 |
| 4 | 7 | 10 | 13 |
| 6 | 8 | 11 | 15 |
如下图所示，会出现 三种情况。
- 数组中选取的数字（图中全黑的位置）刚好是要查找的数字（相等），查找过程结束；
- 选取的数字小于要查找的数字，那么根据数组排序的规则，要查找的数字应该在当前位置的右边或者下边（如下图2.1（a）所示）
- 选取的数字大于要查找的数字，那么要查找的数字应该在当前选取的位置的上边或者左边。
分析：
由上图可知，当不等于要查找的数字的时候会出现两片要查找的区域重叠的情况。我们该怎么考虑呢？
我们可以 从数组的一个角上选取数字来和要查找的数字做比较，情况会变得简单一些。如：首先选取数组右上角的数字9。 由于9大于7，并且还是第4列的第一个（也是最小的）的数字，因此7不可能出现在数字9所在的列。于是我们 把这一列从需要考虑的区域内剔除，之后只需分析剩下的3列（如下图（a）所示）。在剩下的矩阵中，位于右上角的数字是8，同样 8大于7，因此 8所在的列我们也可以剔除。接下来我们只要分析剩下的两列即可（如下图（b） 所示）。
在由剩下的两列组成的数组中，数字2位于数字的右上角。 2小于7，那么要查找的7可能在2的右边，也有可能在2的下边。在前面的步骤中，我们已经发现2右边的列都已经被剔除了每页就是说7不可能出现在2的右边，因此7只有可能出现在2的下边。于是我们 把数字2所在的行也剔除，值分析剩下的三行两列数组（如下图（c)所示）。在剩下的数字中4位于右上角，和前面一样，我们把数字 4所在的行也剔除，最后剩下两行两列数字（如图（d）所示）
在剩下的两行两列4个数字中， 位于右上角的刚好就是我们要查找的数字7，于是 查找过程就可以 结束了。
| 1 | 2 | 8 | 9 |
| 2 | 4 | 9 | 12 |
| 4 | 7 | 10 | 13 |
| 6 | 8 | 11 | 15 |
| （a） | |||
| 1 | 2 | 8 | 9 |
| 2 | 4 | 9 | 12 |
| 4 | 7 | 10 | 13 |
| 6 | 8 | 11 | 15 |
| （b） | |||
| 1 | 2 | 8 | 9 |
| 2 | 4 | 9 | 12 |
| 4 | 7 | 10 | 13 |
| 6 | 8 | 11 | 15 |
| （c） | |||
| 1 | 2 | 8 | 9 |
| 2 | 4 | 9 | 12 |
| 4 | 7 | 10 | 13 |
| 6 | 8 | 11 | 15 |
| （d） | |||
总结
总结上述查找的过程，我们发现如下规律：首先选取数组中右上角的数字。如果该数字 等于要查找的数字， 查找过程 结束；如果该数字 大于要查找的数字， 剔除这个数字所在 列；如果该数字 小于要查找的数字， 剔除这个数字所在的 行。
编码实现
核心算法:
/** * * @param num 被查找的二维数组 * @param rows 行数 * @param columns 列数 * @param number 要查找的数字 * @return 是否找到要查找的数字（number） */ public static Boolean Find(int num[][],int rows,int columns,int number) { Boolean found = false; int row = 0; int column = columns - 1 ; if( rows > 0 && columns >0) { while(row < rows && column >= 0) { if(num[row][column] == number) //查找到 { found = true; break; } else if(num[row][column] >number) { --column; //删除列 } else { ++row; //删除行 } } } return found; }
测试：
public static void main(String[] args) { //初始化数字的值 int num[][]= { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}}; System.out.println(Find(num,4,4,7)); //在数组中 System.out.println(Find(num,4,4,5)); //5不在数组中 }
结果:
truefalse