算法题：二维数组中的查找

84 阅读 0 评论 56 点赞

我是靠谱客的博主震动鱼，最近开发中收集的这篇文章主要介绍算法题：二维数组中的查找，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

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

示例1

输入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true

题目简单明了，最简单的方法，暴力查找，遍历数组每一个元素。但这样效率极其低下，可能需要遍历该数组每一个元素，该题有一个前提条件，数组是按照从左到右从上到下的递增排列的，很容易联想到二分法，但是不同于一维数组的二分法，只有一个方向，如果从左上或者右下开始进行二分，那么大于或者小于都有两个方法，不知道往哪能遍历全，所以只能从右上或者坐下进行，以左下为例，比他大的数都在右边，比他小的数都在他的上边，这样就能定下二分法的方向了。

代码如下：

public class find {
    public static void main(String[] args) {
        int[][] arrays = new int[][] {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
        boolean result = Find(15,arrays);
        System.out.println(result);
    }
    public static boolean Find(int target, int [][] array) {
        if (null == array || array.length == 0 || array[0].length == 0){
            return false;
        }
        int cols = array[0].length;
        int rows = array.length;
        for (int i = rows - 1; i >= 0 ; i --) {
            for (int j = 0; j < cols  ; j ++) {
                if (target == array[i][j]){
                    return true;
                }else if (target > array[i][j]){
                    continue;
                } else {
                    break;
                }
            }
        }
        return false;
    }
}

这样每次可以减少一行或者一列的范围，效率加强不少。