剑指Offer之维数组中的查找

题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
假设二维为m行n列，最直观的方法是遍历数组，时间复杂度为O(m*n):

    public boolean find(int target, int [][] array) {
        if(array==null||array.length==0||array[0].length==0){
            return false;
        }
        if(target<array[0][0]||target>array[array.length-1][array[0].length-1]){
            return  false;
        }
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[0].length;j++){
                if(array[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }

O(m*n)的时间复杂度是令人难以接受的，根据题目中二维数组行列都是递增的条件，可以优化算法，思路如下：
目标数target与数组右上角数字比较，如果target比较大，舍弃数组第一行，继续跟右上角数字比较；如果target比较小，舍弃数组最后一列，继续跟右上角数字比较，实现代码如下：

    public boolean find(int target, int [][] array) {
        if(array==null||array.length==0||array[0].length==0){
            return false;
        }
        if(target<array[0][0]||target>array[array.length-1][array[0].length-1]){
            return  false;
        }
        int i=0,j=array[0].length-1;
        while(j>=0&&i<array.length){
            int item=array[i][j];
            if(target==item){
                return true;
            }else if(target>item){
                i++;
            }else{
                j--;
            }
        }
        return false;
    }