[编程题]二维数组中的查找

二维数组中的查找

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

分析：

• 同一行中元素从小到大排列；
• 同一列中元素从小到大排列；

方法1：暴力解法

public class Solution {
    public static boolean Find(int target, int [][] array) {
        if(array == null || array.length == 0 || array[0].length == 0)
            return false;

        int len1 = array.length;
        int len2 = array[0].length;
        for(int i = 0; i < len1; i++) {
            for(int j = 0; j < len2; j++){
                    if(array[i][j] == target)
                        return true;
                }
        }    
        return false;
    }

方法2：遍历每行进行二分查找

public class Solution {
    public static boolean Find(int target, int [][] array) {
        if(array == null || array.length == 0 || array[0].length == 0)
            return false;

        int len1 = array.length;
        int len2 = array[0].length;
        for(int i = 0; i < len1; i++) {
            if(target == array[i][0] || target == array[i][len2 - 1])
                return true;
            else if(target < array[i][0])
                return false;
            else if(target > array[i][len2 - 1])
                continue;
            else {
                if(binaryFind(array[i], target))
                    return true;
            }
        }

        return false;
    }

    public static boolean binaryFind(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(arr[mid] == target)
                return true;
            else if(arr[mid] > target)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return false;
    }
}

方法3：从左下角开始查找

左下角元素m是行中最小的，是一列中最大的。

• 当m == target时，查到结果，直接返回；
• 当m > target时，因为m是一行中最小的，所以向上移动一行，继续查找；
• 当m < target时，因为m是一列中最大的，所以向右移动一列，继续查找。

public class Solution {
        public static boolean Find(int target, int [][] array) {
        if(array == null || array.length == 0 || array[0].length == 0)
            return false;

        int len1 = array.length;
        int len2 = array[0].length;
        int i = len1 - 1;
        int j = 0;
        while(i >= 0 && j < len2) {
            int m = array[i][j];
            if(m == target)
                return true;
            else if(m > target)
                i--;
            else
                j++;
        }

        return false;
    }
}

方法4：从右上角开始查找

右上角元素是一行中最大的，是一列中最小的。

• 当m == target时，找到结果直接返回；
• 当m > target时，因为m是一列中最小的，所以向左移动一列，继续查找；
• 当m < target时，因为m是一行中最大的，所以想下移动一行，继续查找。

public class Solution {
        public static boolean Find(int target, int [][] array) {
        if(array == null || array.length == 0 || array[0].length == 0)
            return false;

        int len1 = array.length;
        int len2 = array[0].length;
        int i = 0;
        int j = len2 - 1;
        while(i < len1 && j >= 0) {
            int m = array[i][j];
            if(m == target)
                return true;
            else if(m > target)
                j--;
            else
                i++;
        }

        return false;
    }
}