剑指Offer二维数组查找

二维数组查找

题目描述

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

思路

1557045150828.png

箭头方向表示数值大小增长方向。可以看出A点是一个类似于中值的存在，小于A的值在它的上方，大于A的值在它的右边以及右上方（B的值大于等于A）。因此，可以将A点作为起始比较的点。当小于A时，继续向上方寻找；当等于A时，找到；当大于A时，先往右边寻找，如果找不到，再向右上方寻找。这样一步一步缩小查找范围，并且这是一个类似递归的过程。

注意

该问题最需要考虑的是边界问题和容错性：
（1）当array={{}}时；
（2）向上方，右方，右上方寻找时，需要考虑是否越界。

代码

public class Solution {
    public static boolean Find(int target, int [][] array) {
        //首先获取array的size
        boolean result=false;
        int row = array.length;
        int col = array[0].length;
        System.out.println("row");
        System.out.println(row);
        if(col !=0){
            result=Findloop(target, array,row-1,0);
        }

        return result;
    }
    public static boolean Findloop(int target, int [][] array,int rowkey,int colkey){
        boolean status=false;
        if(target < array[rowkey][colkey]){
            if (rowkey>0){
                status=Findloop(target, array,rowkey-1,colkey);
            }
        }
        if(target == array[rowkey][colkey]){
            status=true;
        }
        if(target > array[rowkey][colkey]){
            if(colkey<array[0].length-1){
                for (int i =colkey+1;i<array[0].length;i++){
                    if (target==array[rowkey][i]){
                        status=true;
                        break;
                    }
                    if (target<array[rowkey][i]){
                        break;
                    }
                }
                if(status==false && rowkey>0){
                    status=Findloop(target, array,rowkey-1,colkey+1);
                }
            }


        }
        return status;
    }


    public static void main(String[] args) {
        int target=16;
        int [][] array={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
        for (int i = 0;i<array.length;i++){
            for(int j= 0; j<array[i].length;j++){
                System.out.print(array[i][j]);
                System.out.print(" ");
            }
            System.out.print("\n");
        }
        boolean statue=Find(target,array);
        if(statue==true){
            System.out.print("有");
        }else {
            System.out.print("无");
        }
    }
}