题解 | #二维数组中的查找#

代码 1.0 错误

思路：

1、数组看作一个矩形区间区间分成四块

2、 target与当前区间第一行的中间元素x比较大小

target>x时，target在当前区间的右半边；

target<x时，target在当前区间的左半边；

2、 target与当前区间第一列的中间元素y比较大小

target>y时，target在当前区间的下半边；

target<y时，target在当前区间的上半边；

3、查找范围缩小为原区间的四分之一

4、重复上述步骤

5、不知哪里有逻辑上的错误

package Find_and_sort;
//版本 1.0  （没有写完）
public class Find_ {
    public static void main(String[] args) {
        Solution_Find solution_find = new Solution_Find();
        int target=16;
        int [][] array=new int[][]{{1,2,3,4},{5,7,9,11},{6,8,16,17}};
        boolean res=solution_find.Find(target,array);
        System.out.println(res);


    }
}
class Solution_Find {
    public boolean Find(int target, int [][] array) {
        //返回结果 空数组情况
        if (array.length==0){
            return false;
        }
        int res[]=new int[9];
        int lengh_x=array.length;
        int length_y=array[0].length;
        //返回结果 越界<min or >max
        int x=lengh_x/2;
        int y=length_y/2;
        int head_x=0;
        int tail_x=array.length-1;
        int head_y=0;
        int tail_y=array[0].length-1;
        while (res[0]!=-1001){
            res=fenqu(target,array,x,lengh_x,head_x,tail_x,y,length_y,head_y,tail_y);
            //int res[]=new int[]{0flage,1x,2length_x,3head_x,4tail_x,5y,6length_y,7head_y,8tail_y};
            //更新分区数据
            x=res[1];lengh_x=res[2];head_x=res[3];tail_x=res[4];
            y=res[5];length_y=res[6];head_y=res[7];tail_y=res[8];
            //找到了 直接退出循环 res[0]=-1001
            //这次没找到 继续找   res[0]=-2001
            //根本找不到 退出     res[0]=-3001
            if (res[0]==-3001){
                break;
            }
        }
        //返回最终结果
        if (res[0]==-1001){
            return true;
        }
        else{
            return false;
        }
    }
    public int [] fenqu(int target,int [][] array,int x,int length_x,int head_x,int tail_x,int y,int length_y,int head_y,int tail_y){
        // 1、将二位数组分成四个区
        // 2、确定target所在区域
        // 3、返回所在区域的数据:
        //    x length_x x方向的取值范围{head_x,tail_x},
        //    y length_y y方向的取值范围{head_y,tail_y}
        //int res[]=new int[8];
        //设置一个标记 flage 一般情况：找到目标返回-1001,未找到目标返回-2001(暂未找到 继续找)
        //                 特殊情况：找到目标返回-1001,未找到目标返回-3001(说明目标不在该数组中)
        int flage=-2001;
        //特殊情况的分区 只剩一个元素
        if (length_x==1&&length_y==1){
            if (target==array[head_y][y]){
                flage=-1001;
            }
            else{
                flage=-3001;
                System.out.println("target不在该数组中");
            }
        }
        //一般情况的分区
        else{
            //左右分区 y方向(横)
            if (target==array[head_y][y]){
                flage=-1001;
                System.out.println("在当前分区y方向的中点处找到target");
            }//
            if (target<array[head_y][y]){//左分区
                //y已知
                length_y=length_y/2;//分区长度
                //y方向的取值范围
                head_y=y-length_y;
                tail_y=y-1;
                y=length_y/2;//新分区 y方向的中点
            }
            if (target>array[head_y][y]){//右分区
                length_y=length_y-(length_y/2);//分区长度
                //y方向的取值范围
                head_y=y;
                tail_x=y+length_y-1;
                y=length_y/2;//新分区 y方向的中点
            }
            //上下分区 x方向(纵)
            if (target==array[x][head_x]){
                flage=-1001;
                System.out.println("在当前分区x方向的中点处找到target");
            }
            if (target<array[x][head_x]){//上分区
                //x已知
                length_x=length_x/2;//分区长度
                //x方向的取值范围
                head_x=x-length_x;
                tail_x=x-1;
                x=length_x/2;//新分区 x方向的中点
            }
            if (target>array[x][head_x]){
                length_x=length_x-(length_x/2);//分区长度
                //x方向的取值范围
                head_x=x;
                tail_x=x+length_x-1;
                x=length_x/2;//新分区 x方向的中点
            }
        }
        //返回结果
        int res[]=new int[]{flage,x,length_x,head_x,tail_x,y,length_y,head_y,tail_y};
        return res;


    }
}

代码 2.0 正确

思路：

target与左下角元素p(x,y)比较

target>p时 x不变 y+1；

target<p时 x-1 y不变；

class Solution_Find {
    public boolean Find(int target, int [][] array){
        //特殊情况
        //判断二维数组为空！！！
        if ((array==null||array.length==0)||(array.length==1&&array[0].length==0)){
            return false;
        }
        else{
            int x= array.length-1;
            int y=0;
            //一般情况
            while(true){
                if (array[x][y]==target) {
                    return true;
                }
                if (array[x][y]<target){
                    y=y+1;
                    if (y==array[0].length){
                        return false;
                    }
                }
                if (array[x][y]>target){
                    x=x-1;
                    if (x<0){
                        return false;
                    }
                }
            }

        }

       
    }
}