二维数组中的查找 -----------《剑指Offer》--(Java版)

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

1 2  3    4     5

3 5  7    8     9

6 8 11  22  33

 

1. 最暴力最无脑的是遍历，在这里我就不写了，如果写不出来遍历，最好还是重新学学Java语法。

2. 稍微优化一点点就是遍历每一行，然后在每一行中进行二分搜索.

二分搜索的核心代码：

                int head = 0, last = array[x].length - 1;
                while (head <= last) {
                    int mid = (head + last) / 2;
                    if (array[x][mid] == target) {
                        return true;
                    } else if (array[x][mid] > target) {
                        last = mid - 1;
                    } else {
                        head = mid + 1;
                    }
                }

当然Java也有自带的二分搜索方法.

Arrays.binarySearch(int[],int);//当然也支持部分数组搜索

Arrays.binarySearch(long[],long);

Arrays.binarySearch(short[],short);

Arrays.binarySearch(char[],char);

..等

通过部分二分，我们就可以把时间复杂度从O(n*m)变为O(n*log m) 或 O(m * log n)，以及部分剪枝(小于最小值，则break，大于最大值则搜索下一列)

当然这不是最优，因为题目中的条件只使用了一部分.

3. 建立模型

我们每次先从一行的最大值开始找，(因为行的最大值同时也是列的最小值)

如果行的最大值比目标值小，那么进入前一列:(该列的最小值比目标值还小，所以该列被抛弃)。

如果行的最大值比目标值大，那么进入下一行:(该行的最大值都比目标值小，所以该行被抛弃).

    public boolean Find(int target, int[][] array) {
        if(array.length == 0 || array[0].length == 0){
            return false;
        }
        // 先从矩阵的右上角开始找，这样至少可以剪掉一行或一列.
        int x = 0, y = array[0].length - 1;
        return Find(array, target, x, y);
    }

    private boolean Find(int[][] array, int target, int x, int y) {
        if(x == array.length || y == -1){
            return false;
        }
        if (array[x][y] == target) {
            return true;
        } else if (array[x][y] > target) {
            // 说明矩阵的最后一列无用
            return Find(array, target, x, y - 1);
        } else {
            // 说明矩阵剩余的第一行无用
            return Find(array, target, x + 1, y);
        }
    }