二分查找-二维数组中的查找

题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例1
输入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true

解题思路

利用二分查找和递归的思路，针对如上图所示的数组：
用【l1,r1】表示横坐标范围【0,3】，【l2,r2】表示横坐标范围【0,3】
先找出横，纵坐标的中间值用【m1,m2】表示。示例中就是【1,1】
判断【1,1】位置与目标值target的大小关系
假如target=4，则array【1,1】=4=target 返回true
假如target=7，则array【1,1】=4<target,则变成在如下图中的红色部分和绿色部分进行查找。递归调用即可

假如target=2，则array【1,1】=4>target,则变成在如下图中的红色部分和绿色部分进行查找。递归调用即可

这样便可以把问题递归处理，但是要注意判断数组的上下标越界情况

public class Solution {
    public boolean Find(int target, int [][] array) {
        //117ms  18188KB
        if(array==null) return false;
        if(array.length==0 || array[0].length==0) return false;
        int n=array.length-1;
        int m=array[0].length-1;
        return search(target,array,0,n,0,m);
    }
    public boolean search(int target, int [][] array,int l1,int r1,int l2,int r2){
        if(l1==r1 && l2==r2) return array[l1][l2]==target;
        int m1=l1+(r1-l1)/2;
        int m2=l2+(r2-l2)/2;
        System.out.println(m1+" "+m2+"*****"+array[m1][m2]);
        //需要判断数组下标的合法性。
        if(array[m1][m2]<target){
            //l2小于等于m2与l1小于等于r1一定成立
            //所以应判断是否满足m1+1<=r1 && m2+1<=r2，不满足则说明往下或者往右没有了
            if(m1+1<=r1 && m2+1<=r2) return search(target,array,m1+1,r1,l2,m2)||search(target,array,l1,r1,m2+1,r2);
            else if(m1+1<=r1) return search(target,array,m1+1,r1,l2,m2);
            else if(m2+1<=r2) return search(target,array,l1,r1,m2+1,r2);
            else return false;
        }
        else if(array[m1][m2]>target){
            //同理判断是否满足m1-1>=l1 && m2-1>=l2，不满足则说明往上或者往左没有了
            if(m1-1>=l1 && m2-1>=l2) return search(target,array,l1,m1-1,m2,r2)||search(target,array,l1,r1,l2,m2-1);
            else if(m1-1>=l1) return search(target,array,l1,m1-1,m2,r2);
            else if(m2-1>=l2) return search(target,array,l1,r1,l2,m2-1);
            else return false;
        }
        else{
            return true;
        }
    }
}