二维“有序”数组查找问题的解决| 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，诶一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否包含了该整数。 |
例如下面的二维数组就是每行、没列都递增排序。如果在这个数组中查找数字7，则返回true（找得到）；如果查找数字5，由于数组不含该数字，则返回false。 如下图所示，会出现三种情况。- 数组中选取的数字（图中全黑的位置）刚好是要查找的数字（相等），查找过程结束；
- 选取的数字小于要查找的数字，那么根据数组排序的规则，要查找的数字应该在当前位置的右边或者下边（如下图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，于是查找过程就可以结束了。 注：矩阵中加颜色的的区域是下一步查找的范围。总结 总结上述查找的过程，我们发现如下规律：首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在列；如果该数字小于要查找的数字，剔除这个数字所在的行。
编码实现核心算法: /** * * @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
