二维数组查找
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 根据题意输入的数组可能如下：
对于这种情况可以直接折中查找，但是输入的数组更有可能是如下情况：
对于这种情况直接折中就不太适用，但是根据题意可知，每一行的最小数字出现在最左边，每一列最小数据一定出现在最上方，我们可以根据此特性来排除数据。
假设需要查找2.5，如果选取5与输入的数据比较，大于要查找的数目，则查找的数据必然不会出现在最后一列，可以排除一列，如图
依次类推，可以每次排除一列.直到剩下两列，2小于2.5，无法排除2所在的列。
然后根据行的最小数字进行判定，首先将5与2.5比较，大于2.5，可以排除最后一列
依次类推，剩余两行两列时，判断2<2.5，判定2.5必然出现在第二行的1、2列，然后编列这两个数字，并未找到2.5，可以数组中没有出现此数字。
代码：
1 /*
2 * 寻找二维数组内是否包含某一个数字
3 */
4 public class FindInArray {
5
6 public Boolean Find(int target, int[][] array){
7 Boolean found = false;
8 int minRow = 0;
9 int maxColumn = array[0].length - 1;
10 while(minRow<=array.length - 1 && 0<=maxColumn){
11 if(array[0][0]>target || array[array.length - 1][maxColumn]<target){
12 break;
13 }
14 if(array[minRow][maxColumn] == target ){
15 found = true;
16 break;
17 }else if(array[minRow][maxColumn] > target){
18 maxColumn--;
19 }else{
20 minRow++;
21 }
22 }
23 return found;
24 }
25 /**
26 * @param args
27 */
28 public static void main(String[] args) {
29 // TODO Auto-generated method stub
30 int[][] testArr = {{1,2,3,4,6},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20}};
31 System.out.println(new FindInArray().Find(12,testArr));
32 }
33
34 }
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。