题目描述

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

数组不一定等长

方法一:暴力求解

遍历,然后挨个比较就可以了

public class Solution {
    public boolean Find(int target, int [][] array) {
        int m = array.length;
        for(int i=0; i<m; i++){
            for(int j=0;j<array[i].length;j++){
                if(array[i][j]==target)
                    return true;
            }
        }
        return false;
    }
}

方法二:对每一行使用二分查找

public class Solution {
    public boolean Find(int target, int [][] array) {
        int i;
        int m = array.length;
        for(i=0;i<m;i++){
            if (binFind(target, 0, array[i].length -1, array[i])) {
                return true;
            }
        }
        return false;
    }

    public static boolean binFind(int n,int low,int heigh,int[] arr){
        if(low>heigh)
            return false;
        int mid = (low + heigh)/2;
        if(arr[mid]>n){
               return binFind(n, low, mid - 1, arr);
            }
         if(arr[mid]<n){
                return binFind(n, mid + 1, heigh, arr);
            }
        return true;
    }
}

方法三:找规律

找到矩阵的左下角或右上角

以左下角为例:向上走的变小,向右走则变大

public class Solution {
    /*
     * 1 4 7
     * 2 5 8 
     * 3 6 9
     */
    public boolean Find(int target, int [][] array) {
        int m = array.length;
        int i = m -1;
        int j = 0;
        while(i >= 0 && j < array[i].length){
            if(array[i][j]==target){
                return true;
            }else if (array[i][j]>target) {
                i--;
            }else {
                j++;
            }
        }
        return false;
    }
}