剑指offer习题练习

1 二维数组的查找:

• 在一个二维数组中 ,每一行都按照从左到右递增的顺序排列,每一列都按照从上到下递增的顺序排列.
• 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
• 1 2 3 4
• 4 8 12 16
• 5 10 15 20

2 代码实现 :

    public boolean search(int[][] array,int target){
        int len = a.length-1;
        int i=0;
        while (len>=0&&i<a[0].length){
            if(target>a[len][i]){
                i++;
            }else if(target<a[len][i]){
                len--;
            }else {
                return true;
            }
        }
        return false;

    }

3 代码分析 :

因为二维数组是有序的，我们把数组看成M×N矩阵，从左到右，从上到下是依次递增的，所以我们从左下角开始循环，如果要查找的数大于左下角的数，就在右半部分的矩阵中查找（把第一列去掉，变成M×(N-1)的矩阵），因为第一列的最大的数都小于要查找的数。反之，如果要查找的数小于左下角的数，就在上半部分的矩阵中查找(把最后一行去掉，变成(M-1)×N的矩阵)。当遍历到第一行的时候还没有找到，那么就不存在。