[数组]二维数组中的查找

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

a₁₁	a₁₂	a₁₃	a₁₄	...	a_1n
a₂₁	a₂₂	a₂₃	a₂₄	...	a_2n
a₃₁	a₃₂	a₃₃	a₃₄	...	a_3n
a₄₁	a₄₂	a₄₃	a₄₄	...	a_4n
a₅₁	a₅₂	a₅₃	a₅₄	...	a_5n
...	...	...	...	...	...
a_m1	a_m2	a_m3	a_m4	...	a_mn

也即是说，越往右，越往下，得到的数字越大。
这道题采用的是从右上角向左下角走的方法
我们用一个更具体的例子来说明算法原理
随便编的一个表：

1	5	14	23	45	46
7	14	25	29	62	77
8	17	32	33	69	80
19	23	37	45	75	87
40	47	50	62	77	92
45	56	57	72	88	99
63	69	79	80	97	100

比方说我们现在想查找的是64这个数字，找到每行中第一个大于64的格子，在右侧记录，并把所有大于64的格子做标记（我用了很醒目但是也很丑的双井号标记）

1	5	14	23	45	46	不存在
7	14	25	29	62	##77##	第6位77
8	17	32	33	##69##	##80##	第5位69
19	23	37	45	##75##	##87##	第5位75
40	47	50	62	##77##	##92##	第5位77
45	56	57	##72##	##88##	##99##	第4位72
63	##69##	##79##	##80##	##97##	##100##	第2位69

这个位数是不断减小（或持平）的。这是因为。假设a_i,j > 目标值，那么a_i,j的下方，a_i+1,j > a_i,j > 目标值
我们可以看到，他是以一种阶梯状的分布存在。
所以我们从右上角开始，模拟这个下楼梯的过程。如果64这个数字存在，那么他一定会出现在楼梯的边缘处，而我们的行进轨迹采用小了往下走，大了往左走的交替走法
如这个例子，我们就采用
46 - 小了，往下走 -> 77 - 大了，往左走 -> 62 - 小了，往下走 -> 69 - 大了，往左走 -> 33 - 小了，往下走 -> 45 - 小了，往下走 -> 62 - 小了，往下走 -> 72 - 大了，往左走 -> 57 - 小了，往下走 -> 79 - 大了，往左走 -> 69 - 大了，往左走 -> 63 -> 全部走完，没找

这里有个疑问：小了可不可以往右走？

答案是否定的，因为右侧上方至少走过一个格子，向左边走的原因就是那个格子太大了，所以向左移动。而当前已经向下走了若干步了，此时的右侧格子，比之前走过的更大，显然不会是我们要的结果

具体实现：(使用的是JAVA)

public class Solution {
    public boolean Find(int target, int [][] array) {
        //获得行数，列数
        int rowNum = array.length;
        int colNum = array[0].length;
        //初始化在右上角
        int row = 0;
        int col = colNum - 1;
        
        boolean res = false;
        while(row < rowNum && col >= 0){
            //当到达边缘，说明整个查询操作已结束
            if(array[row][col] == target){
                //找到目标值
                res = true;
                break;
            }
            else if(array[row][col] < target){
                //如果当前值<目标值，说明当前值不够大，往下查找
                row++;
            }
            else{
                //如果当前值>目标值，说明当前值过大，往左查找
                col--;
            }
        }
        return res;
    }
}

1	5	14	23	45	46
7	14	25	29	62	77
8	17	32	33	69	80
19	23	37	45	75	87
40	47	50	62	77	92
45	56	57	72	88	99
63	69	79	80	97	100

1	5	14	23	45	46
7	14	25	29	62	77
8	17	32	33	69	80
19	23	37	45	75	87
40	47	50	62	77	92
45	56	57	72	88	99
63	69	79	80	97	100

[数组]二维数组中的查找

推荐阅读更多精彩内容

1	5	14	23	45	46
7	14	25	29	62	77
8	17	32	33	69	80
19	23	37	45	75	87
40	47	50	62	77	92
45	56	57	72	88	99
63	69	79	80	97	100