[数据结构与算法]JAVA Offer 4:二维数组中的查找

欢迎关注公众号：

题目描述：

【思路分析】

该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。如下数组展示的结果，8大于其上边和左边的所有数字。

因此，搜索流程：

a.首先从数组左下角搜索.
b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。
c.查找到target,返回true; 如果越界，返回false;

如果我们把二分值定在右上角或者左下角，就可以进行二分。这里以右上角为例，左下角可自行分析：

1） 设初始值为右上角元素，arr[0][5] = val，目标tar = arr[3][1]
2）接下来进行二分操作：
3）如果val == target,直接返回
4）如果 tar > val, 说明target在更大的位置，val左边的元素显然都是 < val，间接 < tar，说明第 0 行都是无效的，所以val下移到arr[1][5]
5）如果 tar < val, 说明target在更小的位置，val下边的元素显然都是 > val，间接 > tar，说明第 5 列都是无效的，所以val左移到arr[0][4]
6）继续步骤2）

实现代码如下：

package JavaOffer;

public class JavaOffer4 {
    public static void main(String[] args) {
        JavaOffer4 jf4=new JavaOffer4();
        int [][]a={{1,   4,  7, 11, 15},{2,  5,  8, 12, 19},{3,   6,  9, 16, 22},{10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};     
        boolean haveNum=jf4.solution1(a,0);
        System.out.println(haveNum);
    }

    public boolean solution1(int [][]a, int num){
        int row=a.length;//行数
        int col=a[0].length;//列数
        for (int i = col-1; i >0 ; i--){
            if (a[0][i]<num ){
                for (int j=0;j<row;j++){
                    if (a[j][i]==num){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

上述代码运行结果如下，判断0是否在数组中。