二维数组查找

题目描述

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

public boolean Find(int target, int [][] array) {}

思路

1. 对每一行做二分查找
2. 从左下角元素开始（因为这个位置的元素有确定的增大和减小方向，也可以是右上角），若目标比之小则上移一步，若目标比之大则左移一步

解法1

public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){
            if(biDivSearch(array[i],target,0,array[i].length-1))
                return true;
        }
        return false;
    }
    public boolean biDivSearch(int[] array,int target,int begin,int end){
        if(begin>end)
            return false;
        int mid = (begin+end)/2;
        if(array[mid]==target)
            return true;
        else if(array[mid]>target)
            return biDivSearch(array,target,begin,mid-1);
        else
            return biDivSearch(array,target,mid+1,end);
    }

解法2

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